# Approximating matrix with $n>1$ rank as outer product of vectors

I know that matrix $M$ can be represented as outer product of two vectors (lets say $x$ and $y$) if it is of rank 1. Is there any way of approximating vectors $x$ and $y$ such that $|M - x * y|$ is minimal, when $rank(M) >1$ ?

• We never say a matrix is minimal, but say the norm is minimal. Do you mean this? Then which norm do you use? – PSPACEhard Jun 1 '15 at 13:38
• forgive me, i mean $M - x*y$ is "minimal difference" between $M$ and $x*y$. Maybe sum of differences between corresponding elements of $M$ and $x*y$ is good enough metric? – Tomek Jun 1 '15 at 13:57
• It matters how you want them to be close. Do you want the two matrices to map a vector to two images that are close to each other in the euclidean metric? – muaddib Jun 1 '15 at 14:01
• yes, exactly! I need to have corespondent values in matrices as close as possible. – Tomek Jun 1 '15 at 14:11

## 1 Answer

Yes. The singular value decomposition of $$M = U D V^t$$ where $$U$$ and $$V$$ both have orthonormal column-sets, and $$D$$ is diagonal, with non-increasing elements down the diagonal, can be rewritten as

$$M = u_1 d_1 v_1^t + u_2 d_2 v_2^t + \ldots$$

When the diagonal elements $$d_i$$ are all distinct, the first term in this sequence is the rank-1 matrix that best approximates $$M$$ in the sense of the $$L^2$$ norm (i.e., $$d(X, Y) = tr(X^t Y)$$); the sum of the first two terms is the rank 2 best approximation, and so on.

When there are repeated singular values, you need to take some care... but not much. The only problem is that there are multiple rank-1 matrices that are all equally good approximations of $$M$$. (Think of the identity $$2\times2$$ matrix as an example.)