1
$\begingroup$

Let $A \in \mathbb{C}^{n \times m}$ and $B \in \mathbb{C}^{n \times m}$. Let${\Vert\cdot\Vert}_F$ be the Frobenius norm of a matrix. How can we solve the following optimization problem in $X \in \mathbb{C}^{m \times m}$?

$$\begin{equation} \begin{aligned}\label{P} &\min_{X\in \mathbb{C}^{m\times m}} \quad {\Vert AX-B \Vert}_F^2\\ &\begin{array}{r@{\quad}r@{}l@{\quad}l} \text{s.t.} &{\Vert X \Vert}_F = 1 \end{array} \end{aligned} \end{equation} $$

I'm totally a rookie with complex optimization problems. If this problem can't be solved, please give a detailed explanation. Any help would be appreciated.

$\endgroup$
1
  • $\begingroup$ If you square the norm in the constraint, you have a QCQP. $\endgroup$ Commented Oct 18, 2022 at 9:15

2 Answers 2

2
$\begingroup$

A suitable Lagrange functional is $$ L(X,λ)=\frac12\|AX-B\|_F^2+\frac{λ}2(\|X\|_F^2-1) $$ Variation of $X$ in direction $H$ gives at a saddle point \begin{align} 0&={\rm trace}\Bigl((AX-B)^*(AH)\Bigr)+λ\,{\rm trace}(X^*H) \\ &={\rm trace}\Bigl((A^*AX-A^*B+λX)^*H\Bigr) \end{align} which implies $$ X=(A^*A+λI)^{-1}A^*B. $$ The function $\phi(λ)=\|(A^*A+λI)^{-1}A^*B\|_F^2$ tends toward zero for $λ\to\infty$ and has a pole at every singular value of $A$. Thus above the largest singular value is a solution for $\phi(λ)=1$.

$\endgroup$
1
  • $\begingroup$ really appreciate it! $\endgroup$
    – hideyoung
    Commented Oct 17, 2022 at 7:35
1
$\begingroup$

Note that when $Q$ is unitary we have $$\|QX\|_F=\text{Tr}(QXX^*Q^*)=\text{Tr}(XX^*Q^*Q)=\text{Tr}(XX^*)=\|X\|_F$$ We first find the SVD decomposition $A=U\Sigma V^*$, so $$\|AX-B\|_F^2 = \|U\Sigma V^* X - B\|_F = \|U^*(U\Sigma V^* X - B)\|_F=\|\Sigma V^* X - U^*B\|_F$$

Note that $\|V^*X\|=\|X\|=1$, hence let $Y=V^*X$, then $\|Y\|_F=1$ is equivalent to the original constraint. Therefore $$\|AX-B\|_F^2=\|\Sigma Y-U^*B\|_F^2$$ where $\Sigma=\text{diag}(\lambda_1, \dots, \lambda_n)\ge 0$ is a positive semi-definite diagonal matix.

And assume $Y=\begin{pmatrix} Y_1 \\ \vdots \\ Y_n\end{pmatrix}$ where $Y_i$'s the $i$-th row of $Y$, then we have the cost function is $$\sum_{i}\|\lambda_iY_i-b_i\|_2^2$$ where $b_i$ is the $i$-th row of $U^*B$, and $\|\cdot\|_2$ is the standard Euclidean $2$-norm on $\mathbb C^n$.

Let $b_i=\mu_i\tilde{b_i}$ where $\mu_i=\|b_i\|$ and $\|\tilde{b_i}\|=1$ (if $\|b_i\|\not=0$, $\tilde{b_i}$ is unique, otherwise we may take any unit vector), so to have $$\sum_i \|\lambda_i Y_i -\mu_i \tilde{b_i}\|_2^2$$

subjec to the constraint $\sum_i \|Y_i\|_2^2=1$.

If $Y_i$ is not a scalar multiple of $\tilde{b_i}$, then we can always bring it to be one without changing the norm of $Y_i$, hence without violating the contraint to potentially minimize the cost function. This shows we could always assume $Y_i = y_i \tilde{b_i}$, where $y_i\in\mathbb R$. Now we have the following optimization problem that only depends on real variables $y_i$

$$\begin{cases} \min \sum_i (\lambda_iy_i-\mu_i)^2 \\ \text{ s. t. } \sum_i y_i^2=1\end{cases}$$

(We may insist $y_i\ge 0$, but this won't be necessary, since $\lambda_i, \mu_i\ge 0$, the minimizer of the problem would enforce $y_i\ge 0$ anyway.)

This can be solved by Lagrange multiplier, but I couldn't find a simple closed form solution. In fact, I just find a paper on this topic: Minimizing a quadratic over a sphere. It's pretty easy to deduce Lemma (2.3) in our case using the Lagrange multipler, since we have done the diagonalization. Still, it doesn't seem to be have an analytic solution but a numerical method like gradient descent on the unit sphere is easy to implement.

See also the discussion on Mathoverflow.

$\endgroup$
1
  • $\begingroup$ thank you for your help! $\endgroup$
    – hideyoung
    Commented Oct 17, 2022 at 7:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .