Express $\|y\|_2 \leq t$ as a linear matrix inequality (LMI)

171 Views Asked by At

For $y \in \mathbf{R}^n$ and $t \in \mathbf{R}$, show that:

$$\|y\|_2 \leq t ~~\iff~~ F(y) \succeq 0$$

Where $\mathrm{I}$ is the $n \times n$ identity matrix, and

$$F(y) = \begin{pmatrix} t & y_1 & ... & y_n \\ y_1 & t & & \\ \vdots & & \ddots & \\ y_n & & & t \end{pmatrix} = \begin{pmatrix} t & y^T \\ y & t~\mathrm{I} \end{pmatrix}$$

I came across this problem on a few sites/books, but couldn't readily find a solution. I've posted my answer below in the hopes that it might be useful to someone (assuming it is correct).

1

There are 1 best solutions below

0
On BEST ANSWER

Applying the Schur Complement Lemma, we see that $F(y)$ is positive semi-definite if and only if, first, $t \geq 0$ (which is implied from the original inequality since $||y||_2 \geq 0$) and second:

$$t~\text{I} - y \left ( \frac{1}{t}~\text{I} \right ) y^T \succeq 0 \quad~~ \text{or equivalently} ~~\quad t~\text{I} - \frac{y ~ y^T}{t} \succeq 0$$

Now note that $y~y^T$ is a rank-one matrix with the only eigenvalue $y^T y$ or $||y||_2^2$:

$$(y~y^T)y = y(y^Ty)= ||y||_2^2~y$$

Also note that scaling this matrix by $1/t$ scales the eigenvalue by the same amount, and adding $t \text{I}$ shifts all eigenvalues by $t$. Thus, the matrix $t~\text{I} - \left ( 1/t \right ) \left (y ~ y^T \right )$ has eigenvalues:

$$\lambda_1 = t - \frac{y^T y}{t}$$ $$\lambda_{2,...,n} = t $$

Thus, $F(y)$ is positive semi-definite when (in addition to $t \geq 0$):

$$ t - \frac{y^Ty}{t} \geq 0 $$

$$ t^2 \geq y^Ty $$

$$ ||y||_2 \leq t $$

Where we have used the fact that $t \geq 0$ to multiply both sides of the inequality without flipping the sign.