In this paper, we analyze the limiting behavior of the weighted least squares problem $\min_{x\in\Re^n}\sum_{i=1}^p\|D_i(A_ix-b_i)\|^2$, where each $D_i$ is a positive definite diagonal matrix. We consider the situation where the magnitude of the weights are drastically different block-wisely so that $\max(D_1)\geq\min(D_1) \gg \max(D_2) \geq \min(D_2) \gg \max(D_3) \geq \ldots \gg \max(D_{p-1}) \geq \min(D_{p-1}) \gg \max(D_p)$. Here $\max(\cdot)$ and $\min(\cdot)$ represents the maximum and minimum entries of diagonal elements, respectively. Specifically, we consider the case when the gap $g \equiv \min_i 1/(\|D_i^{-1}\|\|D_{i+1}\|)$ is very large or tends to infinity. Vavasis and Ye proved that the limiting solution exists (when the proportion of diagonal elements within each block $D_i$ is unchanged and only the gap $g$ tends to $\infty$), and showed that the limit is characterized as the solution of a variant of the least squares problem called the {\it layered least squares (LLS) problem}. We analyze the difference between the solutions of WLS and LLS quantitatively and show that the norm of the difference of the two solutions is bounded above by $O(\chi_A\bar{\chi}_A^{2(p+1)}g^{-2}\|b\|)$ and $O(\bar{\chi}_A^{2p+3}g^{-2}\|b\|)$ in the variable and the residual spaces, respectively, using the two condition numbers $\chi_A\equiv \max_{B\in {\cal B}} \|B^{-1}\|$ and $\bar{\chi}_A \equiv \max_{B\in {\cal B}} \|B^{-1}A\|$ of $A$, where ${\cal B}$ is the set of all nonsingular $n\times n$ submatrix of $A$, $A = [A_1; \ldots; A_p]$ and $b = [b_1; \ldots; b_p]$. A remarkable feature of this result is the error bound is represented in terms of $A$, $g$ (and $b$) and independent of the weights $D_i$, $i=1, \ldots, p$. The analysis is carried out by making the change of variables to convert the matrix $A$ into a basis lower-triangular form and then by applying the Sharmann-Morrison-Woodbury formula.
Citation
Technical report: *Graduate school of Decision Science and Technology, Tokyo Institute of Technology, 2-12-1, Ookayama, Meguro-ku, Tokyo, 152-8552, Japan. **The Institue of Statistical Mathematics, 4-6-7, Minami-Azabu, Minato-ku, Japan, 106-8569, Japan.