0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.