2
$\begingroup$

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$ ?

$\endgroup$
  • $\begingroup$ We never say a matrix is minimal, but say the norm is minimal. Do you mean this? Then which norm do you use? $\endgroup$ – PSPACEhard Jun 1 '15 at 13:38
  • $\begingroup$ 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? $\endgroup$ – Tomek Jun 1 '15 at 13:57
  • $\begingroup$ 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? $\endgroup$ – muaddib Jun 1 '15 at 14:01
  • $\begingroup$ yes, exactly! I need to have corespondent values in matrices as close as possible. $\endgroup$ – Tomek Jun 1 '15 at 14:11
3
$\begingroup$

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.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.