Set of solutions to the least-squares problem via QR decomposition

Alicia Y. Tsai; Authors: Laurent EI Ghaoui; Contributors: Phan Hoang, Tony Tin, Ha To Tam, Nguyen Van Kep, Le Dinh Nam, Juliette Decugis, Nguyen Quoc Cuong.; Giuseppe C. Calafiore

Set of solutions to the least-squares problem via QR decomposition

The set $\mathbf{S}$ of solutions to the least-squares problem

$\min _x\|A x-y\|_2^2,$

where $A \in \mathbb{R}^{m \times n}$ , and $y \in \mathbb{R}^m$ are given, can be expressed in terms of the full QR decomposition of $A$ :

$A P=Q R, \quad R=\left(\begin{array}{cc} R_{11} & R_{12} \\ 0 & 0 \end{array}\right),$

where $R_{11} \in \mathbb{R}^{r \times r}$ is upper triangular and invertible, $R_{12} \in \mathbb{R}^{r \times(n-r)}, P$ is a permutation matrix, and $Q$ is $m \times m$ and orthogonal.

Precisely we have $\mathbf{S}=\left\{x_0+N z: z \in \mathbb{R}^{n-r}\right\}$ , with $N$ a matrix whose columns span the nullspace of $A$ :

$x_0=P\left(\begin{array}{c} R_{11}^{-1} y_1 \\ 0 \end{array}\right), \quad N=\left(\begin{array}{c} R_{11}^{-1} R_{12} \\ I \end{array}\right) \in \mathbb{R}^{n \times(n-r)}.$

Proof: Since $Q$ and $P$ are orthogonal, we have, with $\bar{x}:=P^T x, \bar{y}:=Q^T y$ :

$A x-y=A P P^T x-y=Q R \bar{x}-y=Q\left(R \bar{x}-Q^T y\right)=Q(R \bar{x}-\bar{y}),$

Exploiting the fact that $Q$ leaves Euclidean norms invariant, we express the original least-squares problem in the equivalent form:

$\min _{\bar{x}}\|R \bar{x}-\bar{y}\|_2.$

Once the above is solved, and $\bar{x}$ is found, we recover the original variable $x$ with $x=P \bar{x}$ .

Now let us decompose $\bar{x}$ and $\bar{y}$ in a manner consistent with the block structure of

$R: \bar{x}=\left(x_1, x_2\right), \bar{y}=\left(y_1, y_2\right),$

with $x_1, y_1$ two $r$ -vectors. Then

$R \bar{x}-\bar{y}=\left(\begin{array}{c} R_{11} x_1+R_{12} x_2-y_1 \\ -y_2 \end{array}\right),$

which leads to the following expression for the objective function:

$\|R \bar{x}-\bar{y}\|_2^2=\left\|R_{11} x_1+R_{12} x_2-y_1\right\|_2^2+\left\|y_2\right\|_2^2.$

The optimal choice for the variables $x_1, x_2$ is to make the first term zero, which is achievable with

$x_1=R_{11}^{-1}\left(y_1-R_{12} x_2\right),$

where $x_2$ is free and describes the ambiguity in the solution. The optimal residual is $\left\|y_1\right\|_2^2$ .

We are essentially done with $x_2=z$ , we can write

$P^T x=\bar{x}=\left(\begin{array}{c} x_1 \\ x_2 \end{array}\right) = \left(\begin{array}{c} R_{11}^{-1} y_1 \\ 0 \end{array}\right)+\left(\begin{array}{c} R_{11}^{-1} R_{12} \\ I \end{array}\right) z,$

that is: $x=P \bar{x}=x_0+N z$ , with

$x_0=P\left(\begin{array}{c} R_{11}^{-1} y_1 \\ 0 \end{array}\right), \quad N=P\left(\begin{array}{c} R_{11}^{-1} R_{12} \\ I \end{array}\right) \in \mathbb{R}^{n \times(n-r)}.$

License

Icon for the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License

License

Share This Book