Decomposition of a matrix in generalized Woodbury identity.

Let $$\mathbf{A}\in \mathbb{R}^{k\times k}$$ be a semidefinite positive matrix and $$\mathbf{X} \in \mathbb{R}^{k \times n}$$ a rectangular matrix. Is there an efficient way to decompose the matrix $$\mathbf{X}$$ into $$\mathbf{V} + \mathbf{W}$$, where the columns of $$\mathbf{V}$$ are contained in the column space of $$\mathbf{A}$$ and the columns of $$\mathbf{W}$$ are orthogonal to it?

I faced this question while reading "A Sherman–Morrison–Woodbury Identity for Rank Augmenting Matrices with Application to Centering" form Kurt S. Riedel.

Any help would be appreaciated.

Use the QR decomposition to obtain a matrix $$\mathbf{Q}$$ whose columns form an orthonormal basis for the column space of $$\mathbf{A}.$$

Then you can set $$\mathbf{V}=\mathbf{Q}\mathbf{Q}^T\mathbf{X}$$ and $$\mathbf{W}=\mathbf{X}-\mathbf{V} =(\mathbf{I}-\mathbf{Q}\mathbf{Q}^T)\mathbf{X}.$$

The columns of $$\mathbf{V}$$ are contained in the column space of $$\mathbf{A},$$ because the leftmost factor of $$\mathbf{Q}\mathbf{Q}^T\mathbf{X}$$ consists of columns that form a basis of that space.

The columns of $$\mathbf{W}$$ are orthogonal to it, because $$\mathbf{Q}^T\mathbf{W} = \mathbf{Q}^T(\mathbf{I}-\mathbf{Q}\mathbf{Q}^T)\mathbf{X} = (\mathbf{Q}^T-\mathbf{Q}^T\mathbf{Q}\mathbf{Q}^T)\mathbf{X} = (\mathbf{Q}^T-\mathbf{I}\mathbf{Q}^T)\mathbf{X} = 0$$

Uniqueness of the solution

Let $$\mathbf{B}$$ be a matrix whose columns form a basis of the column space of $$\mathbf{A}.$$ Assume that there are two solutions $$v_1+w_1=v_2+w_2=x$$ for a column $$x$$ of $$\mathbf{X},$$ such that $$v_1$$ and $$v_2$$ are in the column space of $$\mathbf{B},$$ and $$w_1$$ and $$w_2$$ are orthogonal to it. This means, there are vectors $$u_1$$ and $$u_2$$ such that $$v_1=\mathbf{B}u_1 \\ v_2=\mathbf{B}u_2$$ and $$\mathbf{B}^Tw_1 =0 \\ \mathbf{B}^Tw_2 =0$$ From $$v_1+w_1=v_2+w_2$$ we get $$v_2-v_1 = w_1-w_2.$$ We have $$0= \mathbf{B}^Tw_1-\mathbf{B}^Tw_2 =\mathbf{B}^T(w_1-w_2) \\ =\mathbf{B}^T(v_2-v_1) =\mathbf{B}^T(\mathbf{B}u_2-\mathbf{B}u_1) =\mathbf{B}^T\mathbf{B}(u_2-u_1)$$ $$\mathbf{B}^T\mathbf{B}$$ is invertible (the columns of $$\mathbf{B}$$ form a basis of a subspace of $$\mathbb{R}^k$$). Therefore, we can solve $$\mathbf{B}^T\mathbf{B}(u_2-u_1)=0$$ for $$u_2-u_1.$$ We get $$u_2-u_1=0$$, which in turn means $$v_1=v_2$$ and $$w_1=w_2.$$ Each column of $$\mathbf{X}$$ has a unique decomposition, which means that the whole matrix $$\mathbf{X}$$ has a unique decomposition.

• Nice and clear. Thank you! Commented Dec 28, 2022 at 14:51
• I have being thinking about this, and what happens when $\mathbf{A}$ is singular? Then, the rank of $A$ will be less than $k$, but the rank of $\mathbf{Q}$ will be $k$ as it is an orthogonal matrix, so it spans more than the column space of $\mathbf{A}$... Commented Dec 28, 2022 at 15:20
• You only use the portion of the "whole $Q$" that corresponds to the non-zero part of $R.$ If $A$ is singular, then $R$ will contain some rows full of zeros. Commented Dec 28, 2022 at 15:31
• OK. One last thing regarding the paper I referenced. To apply the results in the manuscript, it is required that $\mathbf{W}^\top \mathbf{W}$ to be invertible. However, once the useful portion of $\mathbf{Q}$ is sliced, $\mathbf{I} - \mathbf{Q}\mathbf{Q}^\top$ has rank $k-\text{rank}(\mathbf{A})$. Is there a way to find a decomposition that also fulfills this? Commented Dec 28, 2022 at 16:57
• @user326159 The decomposition of $\mathbf{X}$ into $\mathbf{V}+\mathbf{W}$ is unique. There is no freedom you can make use of to get a decomposition that fulfills additional criteria. I edited my answer accordingly. Commented Dec 29, 2022 at 0:51