2
$\begingroup$

We know that given a symmetric $n\times n$ matrix $M$ with rank $r$, by SVD, we have $$M = \sum_{i=1}^r\sigma_i u_iu_i^T,$$ with $\sigma_i >0$ for $i = 1,\dots,r$.

We also know that the rank $k<r$ approximation of $M$, $\hat{M}$, in the sense that $\|M-\hat{M}\|$ is minimized is $$\hat{M} = \sum_{i=1}^k \sigma_iu_iu_i^T.$$


My question is, can we further approximate $\hat{M}$, $\tilde{M}$, by adjusting singular/eigenvlaues of $M$?

For example, replace $\sigma_1$ by $\tilde{\sigma}_1$ such that for some matrix norm $\|\cdot\|_?$ $$\|\hat{M}-\tilde{M}\|_?$$ is minimized?

Please suggest me some references or advises, thanks!

$\endgroup$

1 Answer 1

1
$\begingroup$

Vigorously speaking, no. Since you mentioned that $M$ is a symmetric matrix, the SVD you're stating simplifies into the EVD format $M = VDV^T$. Note that the 2-tuple $(V,D)$ are uniquely given by the eigenspace $\mathrm{eig}(M) = \{(\lambda_i, v_i): Mv_i = \lambda_iv_i\}$ of the matrix $M$. This means the matrix is exactly represented by the eigenvalues and the eigenvectors. The rank-$r$ approximation of $M$ follows from the heuristic that supposing $\lambda_1\geq\lambda_2\geq\dots\geq\lambda_n$ and if $\lambda_1 \gg \lambda_{r + 1}$ we can ignore $\lambda_{r+1} \dots \lambda_{n}$. So this time the approximation $\hat{M}$ is uniquely identified by the 2-tuples $\{(\lambda_i, v_i)\}_{i = 1}^r$. This gives $\hat{M} = V_r\mathrm{diag}({\lambda_1}, \dots, {\lambda_r})V_r^T$. So you cannot further approximate a rank-$r$ matrix that gives a ``better" approximation to $M$.

In practice, however, your numerical tools rounds the exact value of $\lambda_i$'s to a certain data space, e.g. 16-bit float or whatever. So one way you may try is to round $\lambda_i$'s up to $\bar{\lambda}_i$'s, say, 2 decimal places and reconstruct the rank-$r$ approximated matrix $\bar{M} = V_r \mathrm{diag}(\bar{\lambda}_1, \dots, \bar{\lambda}_r) V_r^T$ to approximate the matrix $\hat{M}$ using fewer space, while using the same rank.

$\endgroup$

You must log in to answer this question.

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