Optimization Online


An Analysis of Weighted Least Squares Method and Layered Least Squares Method with the Basis Block Lower Triangular Matrix Form

Tomonari Kitahara (kitahara.t.ab***at***m.titech.ac.jp)
Tsuchiya Takashi (tsuchiya***at***sun312.ism.ac.jp)

Abstract: 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.

Keywords: least squares method, weighted least squares method, layered least squares method, linear programming, interior point method

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 2: Applications -- Science and Engineering (Statistics )

Category 3: Convex and Nonsmooth Optimization (Convex Optimization )

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.

Download: [PDF]

Entry Submitted: 05/29/2008
Entry Accepted: 05/29/2008
Entry Last Modified: 05/30/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society