1
$\begingroup$

it is me agian. I am stuck with the following sentence:

Let $A\in\mathbb{R}^{p\times q}$ with $\operatorname{rank}(A)=r<\min(p,q)$. Now by the definition of singular values, there exist a $(q-r+1)$-dimensional subspace $V$ of $\mathbb{R}^q$ such that $\|Av\|\leq\sigma_r(A)\|v\|$ for all $v\in V$.

I do not understand why the inequality holds. The singular value decomposition delivers me orthogonal matrices $U\in\mathbb{R}^{p\times p}$ and $V\in\mathbb{R}^{q\times q}$ which columns form a orthogonal basis of $\mathbb{R}^p$ or $\mathbb{R}^q$ respectively. Since $r<\min(p,q)$, I pick $q-r+1$ vectors and those form my space $V$. Let $v\in V$ be arbitrary.$$\|Av\|=\|U\Sigma Vv\|\leq\|U\|\|\Sigma\|\|V\|\|v\|=\|\Sigma\|\|v\| $$

I do not know why I am allowed to size up with $\sigma_r(A)$ instead of $\sigma_1(A)$.

I am very confused and appreciate every help.

$\endgroup$
  • $\begingroup$ Just to be clear about your notation, are you using the convention that $\sigma_1(A) \geq \cdots \geq \sigma_r(A)$? $\endgroup$ – Branimir Ćaćić Jun 7 '17 at 7:46
  • $\begingroup$ Yes. The singular values are ordered from the largest to the smallest. $\endgroup$ – Hypertrooper Jun 7 '17 at 7:52
2
$\begingroup$

To avoid notational confusion, let's denote the desired $(q-r+1)$-dimensional subspace of $\mathbb{R}^n$ by $W$.

Suppose you have an SVD for $A$, which means $$ A = U \Sigma V^T $$ for $U$ an orthogonal $m \times m$ matrix, $V$ an orthogonal $n \times n$ matrix, and $\Sigma$ the $m \times n$ matrix given by $$ \Sigma_{ij} := \begin{cases} \sigma_i(A) &\text{if $1 \leq i = j \leq r$,}\\ 0 &\text{else.}\end{cases} $$ If you take a closer look at the matrix multiplications above, this is equivalent to saying that the columns $\{U_1,\dotsc,U_m\}$ of $U$ form an orthonormal basis for $\mathbb{R}^m$ and the columns $\{V_1,\dotsc,V_n\}$ of $U$ form an orthonormal basis for $\mathbb{R}^n$ such that $$ AV_i = \begin{cases} \sigma_i(A)U_i &\text{if $1 \leq i \leq r$,}\\ 0 &\text{if $r+1\leq i \leq n$;} \end{cases} $$ in particular, it follows that $\{V_{i+1},\dotsc,V_n\}$ is a basis for $\ker A$. Given this, it's easy to figure out for which values of $i$ you get $$ \|AV_i\| \leq \sigma_r(A) \|V_i\|. $$ So, does this give you a clue as to what your subspace $W$ will be? Mind you, you will need to check that $W$ really does do the job---to do so, you may need to remember that $\{V_1,\dotsc,V_n\}$ is an orthonormal basis for $\mathbb{R}^n$.

$\endgroup$
  • 1
    $\begingroup$ Thank you! It helped a lot. The subspace $W$ will be the span of $V_r,V_{r+1},\ldots,V_n$. $\endgroup$ – Hypertrooper Jun 8 '17 at 15:49

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.