Approximate Low Rank Decomposition of a Matrix

119 Views Asked by At

Consider a (not necessarily symmetric) matrix $M \in \mathbb{R}^{n \times n}$ and a (tall) matrix $A \in \mathbb{R}^{n \times m}$ with $m \ll n$. We are interested in finding a matrix $W^\star \in \mathbb{R}^{m \times m}$ such that

$$W^\star = \arg \min_W \| M - A W A^\top \|_F$$

Is there a closed-form solution in terms of the SVDs of $M$ (and possibly $A$)? Does this regression have a name?

1

There are 1 best solutions below

3
On BEST ANSWER

The problem is given by:

$$ \arg \min_{W} f \left( W \right) = \arg \min_{W} \frac{1}{2} \left\| A W {A}^{T} - M \right\|_{F}^{2} $$

The Derivative is given by:

$$ \frac{d}{d W} f \left( W \right) = {A}^{T} \left( A W {A}^{T} - M \right) A $$

The derivative vanishes at:

$$ \hat{W} = \left( {A}^{T} A \right)^{-1} {A}^{T} M A \left( {A}^{T} {A} \right)^{-1} $$

Remark

You mention low rank yet you didn't define the constraint.
So basically this is just a Least Squares problem.