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$
4
  • $\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
    Commented Jun 1, 2015 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
    Commented Jun 1, 2015 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
    Commented Jun 1, 2015 at 14:01
  • $\begingroup$ yes, exactly! I need to have corespondent values in matrices as close as possible. $\endgroup$
    – Tomek
    Commented Jun 1, 2015 at 14:11

1 Answer 1

4
$\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$

You must log in to answer this question.

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