# Spectral norm minimization

I was reading the use of semidefinite programs to formulate the matrix norm minimization, but I 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. This 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.

1. 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?

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*}