Express $\|y\|_2 \leq t$ como una desigualdad matricial lineal (IML)

Question

Para $y \in \mathbf{R}^n$ y $t \in \mathbf{R}$ Demuéstralo:

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

Dónde $\mathrm{I}$ es el $n \times n$ matriz de identidad, y

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

Me encontré con este problema en algunos sitios/libros, pero no pude encontrar fácilmente una solución. He publicado mi respuesta a continuación con la esperanza de que pueda ser útil a alguien (suponiendo que sea correcta).

Answer 1

En $\| \mathrm y \|_2 \leq t$ obtenemos $\| \mathrm y \|_2^2 \leq t^2$ o,

$$t^2 - \mathrm y^\top \mathrm y \geq 0$$

Dividiendo ambos lados por $t > 0$ obtenemos

$$t - \mathrm y^\top \left( t \,\mathrm I_n \right)^{-1} \mathrm y \geq 0$$

y, utilizando el complemento de Schur, obtenemos finalmente la siguiente LMI

$$\begin{bmatrix} t \, \mathrm I_n & \mathrm y\\ \mathrm y^\top & t \end{bmatrix} \succeq \mathrm O_{n+1}$$

Answer 2

Aplicación de la Complemento de Schur vemos que $F(y)$ es semidefinida positiva si y sólo si, primero, $t \geq 0$ (que se deduce de la desigualdad original, ya que $||y||_2 \geq 0$ ) y segundo:

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

Tenga en cuenta que $y~y^T$ es una matriz de rango uno con el único valor propio $y^T y$ o $||y||_2^2$ :

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

Obsérvese también que al escalar esta matriz por $1/t$ escala el valor propio en la misma cantidad, y añadiendo $t \text{I}$ desplaza todos los valores propios en $t$ . Así, la matriz $t~\text{I} - \left ( 1/t \right ) \left (y ~ y^T \right )$ tiene valores propios:

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

Así, $F(y)$ es semidefinida positiva cuando (además de $t \geq 0$ ):

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

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

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

Donde hemos utilizado el hecho de que $t \geq 0$ para multiplicar ambos lados de la desigualdad sin invertir el signo.