2
$\begingroup$

Given a matrix $A$ (generally speaking, complex and non-square), I want to find an identically-sized matrix $D$ with ${\rm rk} D\le 1$ to minimize the induced operator norm $\|A-D\|_2$. From the Singular Value Decomposition theorem, one can find $D$ with $\|A-D\|_2=\sigma_2(A)$ (the second singular value of $A$). Indeed, this is best possible: for any rank-$1$ matrix $D$, one has $\|A-D\|_2\ge\sigma_2(A)$.

  • Is there any really simple proof of this last inequality?
  • What is the name / reference for it?

(In fact, I was able to find a reference on the Web, but I'd like to double check it.)

Thanks!

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ Eckart-Young-Mirsky Theorem. $\endgroup$
    – Federico Poloni
    Jun 16, 2014 at 11:12
  • 4
    $\begingroup$ Here's a proof: Say rank(D)=1. Then, there are $n-1$ vectors that span nullspace of $D$. Let $A=USV^T$. We can find a nonzero vector $z$ in null(D) $\cap V_2$, so $Dz=0$. Thus, $\|A-D\|^2 \ge \|(A-D)z\|^2 = \|Az\|^2 \ge \sigma_2^2$ ... $\endgroup$
    – Suvrit
    Jun 16, 2014 at 18:34
  • $\begingroup$ sorry for truncated notation: $A=USV^T$, and $V_k$ denotes the space spanned by the top-$k$ right singular vectors of $A$. Also, instead of "we can find a nonzero vector $z$...", I should have said: we can find a nonzero unit vector $z$; also, since $\|Az\|^2 = z^TA^TAz$, using $A=\sum_i \sigma_i u_iv_i^T$ the rest follows... $\endgroup$
    – Suvrit
    Jun 16, 2014 at 21:10
  • $\begingroup$ @Suvrit: this is not "a proof", this is the proof! Very nice! $\endgroup$
    – Seva
    Jun 17, 2014 at 6:04

1 Answer 1

Reset to default
3
$\begingroup$

The proof can be found in Golub, van Loan's "Matrix Computations", Sec 2.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.