Jtdylktuy

Is it possible to express an inequality constraint on the squared Frobenius norm of a matrix $X$:

$$|X|_F^2 = mathop{tr}( X^T X ) le t$$

as a linear matrix inequality?

I want to say that it's:

$$left[begin{array}{cc} I & X \ X^T & tIend{array}right] succcurlyeq 0$$

but I've lost confidence that this is correct since the Schur complement would be $tI - X^TX succcurlyeq 0 $ and I can't figure how the trace gets in there.

There might be a compacter and more elegant way, but one way you can represent it as LMI's is by using intermediate values for each diagonal term of $X^top X$. These can be calculated using

$$
Y_i = X,e_i
$$

with $e_i$ a vector with the $i$th element equal to one and the rest zeros (so $Y_i$ is the $i$th column of $X$), such that $Y_i^top Y_i$ is the $i$th diagonal term of $X^top X$. Then using the Schur complement you can write for every diagonal term an LMI for $Y_i^top Y_i leq alpha_i$, namely

$$
begin{bmatrix}
I & Y_i \ Y_i^top & alpha_i
end{bmatrix} succeq 0,
$$

with $alpha_i in mathbb{R}$. Now a bound for $|X|_F^2$ can be found by summing all $alpha_i$, which should be smaller or equal to $t$

$$
sum alpha_i leq t,
$$

which is also a linear inequality.

By using an intermediate LMI for $X^top X$ you might also be able to write $X^top X preceq M$, with $M = M^top$, as

$$
begin{bmatrix}
I & X \ X^top & M
end{bmatrix} succeq 0.
$$

An upper bound for $|X|_F^2$ would then be $text{Tr}(M)$, so adding the linear inequality $text{Tr}(M) leq t$ would make this system of LMI's equivalent to your problem. To show that $X^top X preceq M$ also implies that $text{Tr}(X^top X) leq text{Tr}(M)$ you can use that the trace of a matrix is equal to the sum of all its eigenvalues. Namely $X^top X preceq M$ is equivalent to $M - X^top X succeq 0$, thus $M - X^top X$ can only have non-negative eigenvalues and therefore $text{Tr}(M - X^top X)$ is the sum of these non-negative eigenvalues, which is also non-negative. The trace inequality $text{Tr}(X^top X) leq text{Tr}(M)$ is equivalent to $text{Tr}(M - X^top X) geq 0$ and in the previous sentence it was shown that it holds when $X^top X preceq M$, thus $text{Tr}(X^top X) leq text{Tr}(M)$ should hold in that case as well.

It can be noted that $M$ might add more degrees of freedom than all $alpha_i$ so might or might not be an attractive alternative of writing the problem as LMI's.