Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to solve this minimization problem: given a matrix $X$ with at least one singular value greater than 1, find

$ \min_Z\; \langle X-Z,X-Z \rangle$ subject to the constraint $ \|Z\| = \max_i\; \sigma_i(Z) \le 1 $, where $\langle A,B \rangle = \mathrm{tr}(AB^\top)$

I'm tempted to just replace the singular values of $X$ that are greater than $1$ with exactly one, but I can't prove that that's correct. It's certainly right for the equivalent vector case of projection onto the $\ell_\infty$-ball.

share|improve this question

1 Answer 1

$\def\tr{\operatorname{tr}}\def\sc#1#2{\langle#1,#2\rangle}\def\scc#1{\sc{#1}{#1}}$I'm not sure whether the transpose in the trace was supposed to imply that these are real matrices; I'll do it for complex matrices using $\sc AB= \tr(AB^*)$ and the result for real matrices will follow. I'll assume distinct non-zero singular values to simplify things; I think you can do the same thing for degenerate and zero singular values with a bit more attention to details.

You can use the singular value decompositions of the two matrices and show that the singular vectors must be the same; it then follows that the singular values of $Z$ are as you say. So let $X=U\Sigma V^*$ and $Z=S\Lambda T^*$ with $U$, $V$, $S$, $T$ unitary, $\Sigma$, $\Lambda$ diagonal and real, $\Sigma,\Lambda\ge0$ and $\Lambda\le1$. Then

$$ \begin{align} \scc{X-Z} &=\scc{U\Sigma V^*-S\Lambda T^*} \\ &= \scc{U\Sigma V^*}+\scc{S\Lambda T^*}-\sc{S\Lambda T^*}{U\Sigma V^*}-\sc{U\Sigma V^*}{S\Lambda T^*} \\ &= \tr U\Sigma V^*V\Sigma^* U^*+\tr S\Lambda T^*T\Lambda^* S^*-\tr S\Lambda T^*V\Sigma^* U^*-\tr U\Sigma V^*T\Lambda^* S^* \\ &= \tr\Sigma\Sigma^*+\tr \Lambda\Lambda^*-2\Re\tr S\Lambda T^*V\Sigma^* U^*\;. \end{align} $$

Let $M=U^*S$ and $N=T^*V$ (so $M$ and $N$ are unitary), let $M=\mathrm e^{\mathrm iH}$ and $N=\mathrm e^{\mathrm iK}$ with $H$ and $K$ Hermitian, and vary $H$ and $K$ in $\Re\tr M\Lambda N\Sigma^*$. For each free parameter in $H$ we get an equation of the form $\Re\tr\mathrm iP_{kl}M\Lambda N\Sigma^*=0$, where $P_{kl}$ is an elementary Hermitian matrix, and similarly $\Re\tr\mathrm iP_{kl}\Sigma^*M\Lambda N=0$ from varying $K$. Forming linear combinations of these and using the assumption that the singular values in $\Sigma$ are distinct and non-zero, we can deduce from $\Re\tr\mathrm i(P_{kl}\Sigma^*\pm\Sigma^*P_{kl})M\Lambda N=0$ that $M\Lambda N$ is real and diagonal. Then it follows from the uniqueness of the singular value decomposition that $M\Lambda N=\Lambda$, so $M$ and $N$ contain only phase factors, and thus $S=U$ and $T=V$ up to phase factors that cancel in $Z$. Then

$$ \scc{X-Z} =\scc{U\Sigma V^*-U\Lambda V^*}=\scc{\Sigma-\Lambda}\;, $$

and it's clear that this is minimized by your correct guess.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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