0
$\begingroup$

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.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Nice and clear. Thank you! $\endgroup$
    – user326159
    Dec 28, 2022 at 14:51
  • $\begingroup$ 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}$... $\endgroup$
    – user326159
    Dec 28, 2022 at 15:20
  • 2
    $\begingroup$ 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. $\endgroup$
    – Reinhard Meier
    Dec 28, 2022 at 15:31
  • $\begingroup$ 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? $\endgroup$
    – user326159
    Dec 28, 2022 at 16:57
  • $\begingroup$ @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. $\endgroup$
    – Reinhard Meier
    Dec 29, 2022 at 0:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .