Prove the closed-form solution of low-rank linear regression.

255 Views Asked by At

Given matrices $X \in \mathbb{R}^{n \times d}$ and $Y \in \mathbb{R}^{n \times p}$, consider the linear regression problem in $W \in \mathbb{R}^{d \times p}$

$$\min_{W \in \mathbb{R}^{d \times p}}~\|Y-XW\|_{F}^{2}$$

In general, the closed-form solution to this problem is given by

$$\tilde{W} = X^\dagger Y$$

where $\cdot^\dagger$ denotes the pseudo-inverse.

If we impose a low-rank constraint on $W$, then the linear regression problem becomes

$$\begin{align}\min_{W}~\|Y-XW\|_{F}^{2} \\ \text{s.t.}~\text{rank}(W)\leq R\end{align}$$

How to show that the solution of this problem is $\tilde{W}P$ where $P$ is the matrix of the orthogonal projection onto the space spanned by the top-$R$ right singular vectors of $Y$?

Thank you for your help!

1

There are 1 best solutions below

0
On

By referring to Optimal Exact Least Squares Rank Minimization (or see DOI), I obtained the following derivation. But to be honest, I am not sure it is correct or not. If you have any new idea about this question, please let me know. Thank you!

Suppose the SVD of $Y$ is $Y=UDV^\top$ where $U\in\mathbb{R}^{n\times r},D\in\mathbb{R}^{r\times r},V\in\mathbb{R}^{p\times r},r=\min\{n,p\}$, then

$$\begin{align}\min_{W}~\|X^\dagger Y-W\|_{F}^{2} \\ \text{s.t.}~\text{rank}(W)\leq R \end{align}$$ can be written as $$\begin{align}\min_{W}~\|X^\dagger Y-W\|_{F}^{2} \\ \text{s.t.}~\text{rank}(W)\leq R \end{align}$$ $$\Rightarrow\begin{align}\min_{W}~&\|X^\dagger YV-WV\|_{F}^{2} \\ \text{s.t.}~&\text{rank}(W)\leq R \end{align}$$

Define $Q=WV$, recall that Frobenius-norm is invariant under any orthogonal transformation, we have $$\begin{align}\min_{Q}~&\|X^\dagger YV-Q\|_{F}^{2} \\ \text{s.t.}~&\text{rank}(Q)\leq R \end{align}\quad\Rightarrow\quad \min_{Q}~\|X^\dagger YV_{R}-Q\|_{F}^{2}$$ where $V_{R}$ consists of the top-$R$ right singular vectors of $Y$.

Therefore, the solution of this problem is $X^\dagger YP$ where $P$ is the matrix of the orthogonal projection onto the space spanned by the top-$R$ right singular vectors of $Y$.