0
$\begingroup$

For a symmetric p.s.d matrix $A \in \mathcal{R}^{n\times n}$, we can calculate its SVD as $A=USV^T$, then we can use the truncated SVD to approximate it with a low-rank matrix $\tilde{A} = \sum_i^dU_iS_iV_i^T$, my question is about the element-wise comparison between $A$ and $\tilde{A}$.

Empirically, I notice that it looks like for any $i$ and $j$, $A_{i,j}\tilde{A}_{i,j} > 0$, which means that truncated SVD will never flip the sign of an element.

Is this something known, or can we try to prove it?

Here is the script that I tried:

r = 0;
for i = 1:1000
    A = rand(10);
    A = A*A.';
    [u, s, v] = svd(A);
    s2 = s;
    s2(3:end,3:end) = zeros(8);
    B = u*s2*v.';
    Z = A.*B;
    r = r + sum(sum(Z<0));
end
r
$\endgroup$

1 Answer 1

4
$\begingroup$

It's not true.
Consider the $3 \times 3$ PSD matrix $$ \pmatrix{3 & \epsilon & -3\cr \epsilon & 5 & -1\cr -3 & -1 & 4\cr} $$ where $\epsilon > 0$ is small. Its rank-$2$ approximation will have negative $(1,2)$ and $(2,1)$ elements.

$\endgroup$

You must log in to answer this question.

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