# Frobenius norm minimization with Frobenius norm constraint

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

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.

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

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

• really appreciate it! Commented Oct 17, 2022 at 7:35

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.