1
$\begingroup$

I came across the following exercise in preparation for a test.

Let $A \in \mathbb{R}^{n \times m}$ with rank $r < \min\{n,m\}$. Use SVD of $A$ to show that for every $\epsilon >0$ (no matter how small), there existsa full-rank matrix $A_{\epsilon} \in \mathbb{R}^{n\times m}$ such that $|| A - A_\epsilon ||_{2} < \epsilon$.

I am really puzzled on how to approach this exercise. From my understanding $$ A - A_\epsilon = \underset{n\times n}{U} \ \underset{n \times m}{\Sigma} \ \underset{m\times m}{V^{T}} - \underset{n\times n}{U} \ \underset{n \times m}{\Sigma_\epsilon} \ \underset{m\times m}{V^{T}} = U(\Sigma - \Sigma_\epsilon)V^{T}.$$ Then $\Sigma$ is diagonal matrix with singular values ranging from $\sigma_1$ to $\sigma_{\min\{n,m\}}$ and $\Sigma_\epsilon$ having singular values from $\sigma_1$ to $\sigma_m$ since $A_\epsilon$ is of rank $m$.

Then since $\min\{n,m\} \le m$ $$ \Sigma - \Sigma_\epsilon = \begin{pmatrix} \sigma_1 & & & \\ & \ddots & \\ & & \sigma_n & \\ & & & 0\end{pmatrix} - \begin{pmatrix} \sigma_1 & & & \\ & \ddots & \\ & & \sigma_{\min\{n,m\}} & \\ & & & 0\end{pmatrix} = \begin{pmatrix} 0& & & \\ & \ddots & \\ & & \sigma_? & \\ & & & 0\end{pmatrix}$$ So since a singular value exists for the matrix difference above, $|| A - A_\epsilon ||_2 = \sigma_?$ which has to be small since $\sigma_1 > \sigma_2 > \dots > \sigma_r$, and here this $\sigma_?$ is among among the last in the sequence.

I am most likely writing non-sense, I am aware of that, I don't know how to proceed, can anyone give me some hint or idea ?

$\endgroup$
1
  • $\begingroup$ You don't know that $A_\varepsilon$ has rank $m$. You don't know if $m<n$ or viceversa. You should set $p=min(m,n)$, and think in terms of $p$ rather than $m$ or $n$. $\endgroup$
    – bartgol
    Mar 19, 2021 at 18:18

2 Answers 2

1
$\begingroup$

You are very close. The proof needs a couple of ingredients:

  • What is the norm of A (say the 2-norm, since they are all equivalent) in terms of $\Sigma$? And what's the norm of $\Sigma$ in terms of the $\sigma_i$'s?
  • The simples way to perturb $\Sigma$ is to let $\Sigma_\varepsilon$ have the first $r$ singluar values matching those of $\Sigma$.

If you write $\Sigma_\varepsilon$ as described above, what would $\|\Sigma_\varepsilon-\Sigma\|$ be? And therefore, what aboud $\|A-A_\varepsilon\|$?

Edit: read further for more details.

You are free to build $A_\varepsilon$ in whatever way you want. The goal is to produce one matrix that is close to A, however peculiar its construction may be. So pick same $A_\varepsilon=U\Sigma_\varepsilon V^T$, with $\Sigma_\varepsilon$ with the same first $r$ singular values as $\Sigma$, and $\sigma_i<\varepsilon$ for $i=r+1,...,p$. (Note: you could pick any values for $\sigma_{r+1},...,\sigma_p$, so long as they are all positive, and all smaller than $\varepsilon$. Then $\|\Sigma-\Sigma_\varepsilon\|=\sigma_{r+1}<\varepsilon$. This proves that $A_\varepsilon$ is arbitrarily close to A. The fact that all its singular values are non zero (small as they may be), implies that $A_\varepsilon$ is full rank. QED.

$\endgroup$
3
  • $\begingroup$ Thank you for answering ; I am not sure for the norm of $A$ in terms of $\Sigma$ but I know there is a theorem that says that $||A||_2 = \max \sigma_i (A)$ , so I suppose that, letting $p := \min\{n,m\}$ , $|| A - A_\epsilon ||_2 = \max \sigma_i (\Sigma - \Sigma_\epsilon)$ ; but here I am not sure what is the difference in length of the sets $\{\sigma\}_i \in \Sigma$ and $\{\sigma\}_i \in \Sigma_\epsilon$. I suppose that doesn't matter since we're taking the maximum anyways ? And since the singular values are decreasing in value as $i$ increases then $|| A - A_\epsilon ||_2 = \sigma_{r+1}$ ? $\endgroup$
    – hexaquark
    Mar 19, 2021 at 18:38
  • $\begingroup$ Correct. If you pick $\Sigma_\varepsilon$ to have the same first $r$ singular values as $\Sigma$, then $\|\Sigma-\Sigma_\varepsilon\|=\sigma_{r+1}$. Therefore... $\endgroup$
    – bartgol
    Mar 19, 2021 at 21:28
  • $\begingroup$ honestly, I am completely clueless as to how to proceed further. How would I even begin to show that $|| A - A_{\epsilon}|| = \sigma_{r+1} < \epsilon $ for $\epsilon$ very small ? Or do I just say; $\sigma_{r+1}$ is very small so $\exists \ 0 < \epsilon < \sigma_{r+1} \ | \ || A - A_{\epsilon}||_{2} < 0$ ? $\endgroup$
    – hexaquark
    Mar 20, 2021 at 1:03
1
$\begingroup$

Note that in the case of square matrices $(n\times n$), there is maybe a shorter proof.

$p(x)=\det(A-xI)$ is a polynomial in $x$ and has at most $n$ roots in $\mathbb C$.

So let's take $A_\epsilon=A-\epsilon I$, we have $\det(A_\epsilon)=\det(A-\epsilon I)=p(\epsilon)$

The number of roots of $p$ being finite, we can always choose $\epsilon$ such that $p(\epsilon)\neq 0$, making $A_\epsilon$ invertible.

$\endgroup$

You must log in to answer this question.

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