Matrix norm minimization and matrix inner product

Question

One of the famous problem in SDP is the matrix norm minimization (see S. Boyd, Convex Optimization, p. 170).

Consider:

\begin{equation}\label{eq:Lasse} \begin{aligned} &\min_{\mathbf{x}} & & \|A(x)-M\|_2 \\ & & & A(x)=-A(x)^T \end{aligned} \end{equation}

Here

1. $x\in \mathbb{R}^n$
2. $A(x)=x_1A_1+\cdots+x_nA_n$, with $A_i\in \mathbb{R}^{n\times n}$ and $A_i=-A_i^T$. So we consider $A_i$ are skew-symmetric. We also assume each column of $A(x)$, $A_i(x)$, $\|A_i\|_2=1$.
3. $M\in \mathbb{R}^{n\times n}$ is given.
4. Here we consider the spectral norm of matrices.

So this SDP finds the optimal solution $x$ to minimize a particular metric between $A(x)$ and $M$ and this metric is quantified by $\|A(x)-M\|$. Here we suppose $x^*$ is the optimal solution.

My question is that is $x^*$ the optimization solution of the following problem?

\begin{equation} \begin{aligned} &\max_{\mathbf{x}} & & \langle A(x), M\rangle \\ &\text{ s.t.} & & A(x)=-A(x)^T \end{aligned} \end{equation}

---

The motivation for asking this problem is from the fact that in the vector case (assume $\|c\|_2=1$)

\begin{equation} \begin{aligned} &\min_{\mathbf{x}, \|x\|_2=1} & & \|x-c\|_2 \end{aligned} \end{equation}

the optimal solution is $x^*=c/\|c\|_2$. And $x^*$ is also the solution of the following problem

\begin{equation} \begin{aligned} &\max_{\mathbf{x}, \|x\|_2=1} & & \langle x, c\rangle. \end{aligned} \end{equation}

So not sure if it also fits to the case of matrices. Any reference or papers are welcome.

---

Also if it is not the same for spectral norm, will it be the same for Frobenius norm? why and why not?

Sincerely appreciate your help.

Answer 1

The comments to this question of mine show that, in general, the operator-norm and Frobenius-norm minima are distinct for this problem.

Let me summarize the argument here. Let $M=diag(\alpha,\beta,\gamma)$ be a $3\times 3$ complex matrix, and $A_i=I$ for each $i$ (there are symmetric rather than antisymmetric, but it is enough to pre-multiply both $M$ and the $A_i$ by an antisymmetric orthogonal matrix to fix this, as these norms are orthogonally-invariant). So the problem becomes $\min_{s\in\mathbb{R}} \|sI-M\|$.

Then, the optimal complex multiple of the identity $s\in\mathbb{C}$ to add is the circumcentre of the triangle with vertices $\alpha,\beta,\gamma$ in the operator norm, while in the Frobenius norm it is the centroid of this triangle. And, for a generic triangle, these two centers are different. One can take an example $\alpha,\beta,\gamma$ where both these points are real; hence they are also minima when one restricts the problem to $s \in \mathbb{R}$.

Answer 2

I hope I haven't missed anything here, but isn't the constraint $A(x) = -A(x)^T$ redundant since we know $A_i = -A_i^T$? I would have thought that we necessarily have $$ -A(x)^T = -x_1 A_1^T - \ldots - x_n A_n^T = -A(x). $$

Also, while the spectral norm is well defined, there is no such thing as a spectral inner-product, so I'm not sure exactly what you mean in the dual form.

In the case of the Frobenius norm however, we can flatten the matrices to vectors $a_1,\ldots,a_n, m \in \mathbb{R}^{n^2}$, have a matrix $\tilde A = [ a_1 \cdots a_n ] \in \mathbb{R}^{n^2 \times n}$ (where the $a_i$ are columns vectors that make up $\tilde A$), then write $$ \| A(x) - M \|_F = \| \tilde A x - m \| $$ (as $\|A_i\|_F = \| a_i \|$ where the latter is the usual Euclidian norm of the vector $a_i$) in which case indeed the optimal solution to your problem is going to be the projection of $m$ on to $\mathrm{Span}(a_1, \ldots, a_n)$, which you could write as a maximization of $\langle \tilde A x, m\rangle$ if you are careful.