Spectral norm minimization

Question

I was reading the use of semidefinite programs to formulate the matrix norm minimization but am having trouble trying to understand it. I'd also like to understand it at a more intuitive level.

[Boyd and Vandenberghe: Convex optimization $\S$ 4.6.3]

Matrix norm minimization

Let $A(x) = A_0 + x_1 A_1 + \dots + x_n A_n$, where $A_i \in \mathbf{R}^{p\times q}$. We consider the unconstrained problem $$ \textrm{minimize} \qquad \|A(x)\|_2, $$ where $\|\ \cdot\ \|_2$ denotes the spectral norm (maximum singular value), and $x \in \mathbf{R}^n$ is the variable. Thsi is a convex problem since $\|A(x)\|_2$ is a convex function of $x$.

Using the fact that $\| A \|_2 \leq s$ if and only if $A^TA \preccurlyeq s^2 I$ (and $s \geq 0$), we can express the problem in the form \begin{align} \textrm{minimize} &\qquad s \\ \textrm{subject to} &\qquad A(x)^TA(x) \preccurlyeq sI, \end{align} with variables $x$ and $s$. Since the function $A(x)^TA(x) - sI$ is a matrix convex in $(x,s)$, this is a convex optimization problem with a single $q \times q$ matrix inequality constraint.

1. Where can I see what this fact is talking about? The only thing I read, based on Wikipedia, is that the $L_2$ norm of a matrix is $\|A\|_2 = \sigma_{\max}(A) \le \left(\sum_{i,j} |a_{i,j}|^2\right)^{\frac{1}{2}}$

2. Since $A^TA \preccurlyeq s^2I $ indicate that the matrix $A^TA - s^2I$ is negative semidefinite, if I have a $2\times 2$ matrix $A$, then

   • $\|A\|_2^2 \le s^2 \implies a_{11}^2 + a_{12}^2 + a_{21}^2 + a_{22}^2 \le s^2$
   • $A^TA - s^2I \preccurlyeq 0 \implies s^2(a_{11}^2 + a_{12}^2 + a_{21}^2 + a_{22}^2) - (a_{11}a_{12} + a_{21}a_{22})^2 \le 0 $

   I spent a while looking at this expression but I am still unsure how it explains the fact in point 1.

3. In layman's terms, is the expression saying that the $L_2$ norm of a matrix can only be lesser than its maximum eigenvalue ($s$?) if $A^TA - s^2I$ is negative semidefinite?

Answer 1

As $\|A\|_2=\max_{x\neq 0} \frac{\|Ax\|_2}{\|x\|_2}$ by definition, for every $s\geq 0$, we have \begin{align*} \|A\|_2 \leq s &\iff \frac{\langle Ax,Ax\rangle}{\langle x,x\rangle}=\frac{\|Ax\|_2^2}{\|x\|_2^2}\leq s^2 \qquad &\forall x\neq 0\\ &\iff \langle Ax,Ax\rangle\leq s^2\langle x,x\rangle \qquad &\forall x\neq 0\\ &\iff \langle A^TAx,x\rangle- s^2\langle x,x\rangle\leq 0 &\qquad \forall x\neq 0\\ &\iff \langle (A^TA-s^2I)x,x\rangle\leq 0 \qquad &\forall x\neq 0\\ &\iff A^TA\preceq s^2I \end{align*}