6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

$\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.

$\endgroup$

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.