Splitting a least-squares problem in two, quantifying the error

141 Views Asked by At

I have formulated a least-squares problem of the form:

$$\min_{\pmb{x}}\|\pmb{B}\pmb{A}\pmb{x} - \pmb{b}\|^2_2.$$

The resulting solution is given by (I assume $(\pmb{A}^T\pmb{B}^T\pmb{B}\pmb{A})$ is invertible):

$$\pmb{x}^* = (\pmb{A}^T\pmb{B}^T\pmb{B}\pmb{A})^{-1}\pmb{A}^T\pmb{B}^T\pmb{b}.$$

The matrix $(\pmb{A}^T\pmb{B}^T\pmb{B}\pmb{A})$ has turned out to be fairly ill-conditioned in my case, however, so I have decided to split the problem into two parts for efficiency reason (I am using an iterative solver):

$$\min_{\pmb{y}}\|\pmb{\pmb{B}y-\pmb{b}}\|^2_2 \implies \pmb{y}^* = (\pmb{B}^T\pmb{B})^{-1}\pmb{B}^T\pmb{b},$$ $$\min_{\pmb{z}}\|\pmb{A}\pmb{z}-\pmb{y}^*\|^2_2 \implies \pmb{z}^* = (\pmb{A}^T\pmb{A})^{-1}\pmb{A}^T\pmb{y}^*,$$

where I have assumed that $(\pmb{B}^T\pmb{B})$ and $(\pmb{A}^T\pmb{A})$ are invertible. I interpret those two steps as two subsequent $l_2$ projections (i.e. $\pmb{b}$ is projected through $\pmb{B}$ into $\pmb{B}\pmb{y}^*$, and then $\pmb{y}^*$ is projected through $\pmb{A}$ into $\pmb{A}\pmb{z}^*$).

Is there a way to analytically asses the quality of:

$$\pmb{z}^* = (\pmb{A}^T\pmb{A})^{-1}\pmb{A}^T(\pmb{B}^T\pmb{B})^{-1}\pmb{B}^T\pmb{b}$$

when compared to:

$$\pmb{x}^* = (\pmb{A}^T\pmb{B}^T\pmb{B}\pmb{A})^{-1}\pmb{A}^T\pmb{B}^T\pmb{b}?$$

I intuitively understand that the closer $\pmb{B}^T\pmb{B}$ is to the identity matrix, the closer those results are. However I would like something more concrete.