Minimize Frobenius norm

Question

My question is the following:

Suppose $M$ is an $n \times n$ symmetric real matrix. I want to find an $n \times n$ symmetric real matrix X such that $|| X -M||_F$ is minimized with the constraint that $U^T X U \succeq 0$ (positive semidefinite), where $U$ is an $n \times d$ matrix, $U^TU = I_d$ and $n > d$. $|| \cdot ||_F$ is the Frobenius norm of matrix. In short: \begin{equation} X^* = \displaystyle \operatorname{argmin}_{X:U^TXU\succeq 0}||X-M ||_F, X, M \in \mathcal{S_n} \end{equation}

Some useful information may be: $U$ can be obtained from eigenvalue decomposition of $BB^T$ or QR decomposition of $B$ in the sense that there exists $Q = [U,V]$ such that $Q^TQ = QQ^T = I_n, U^TB = 0$.

I would like to find a formula or construction based on eigenvalue decomposition or singular value decomposition for M. For example, if the constraint is $X \succeq 0$ instead of $U^T X U \succeq 0$, we can first apply eigenvalue decomposition to $M$ such that $M = Q \operatorname{diag}(\lambda_1,\cdots, \lambda_n) Q^T$, then $X^* =Q \operatorname{diag}(\max\{\lambda_1,0\},\cdots, \max\{\lambda_n,0\}) Q^T $ would minimize $|| X-M ||_F$.

I used CVX package to compute $X^*$ for some examples and I found some interesting facts: $ (X^*-M) B = 0$ where $U^TB=0$ and $X^* -M$ is always positive semidefinite while $M$ and $X^*$ may not be positive semidefinite. Any help or suggestion of what method or tools I should use for these kind of problems would be much appreciated! Thanks~

Answer 1

Here's one approach to solve this problem.

Since $U$ is a thin matrix with orthogonal columns each of which has unit norm it spans a $d$ dimensional subspace within the $n$ dimensional ambient subspace. Now we can see that the constraint that $U^TXU \succeq 0$ is a looser constraint than $X \succeq 0$ since $X$ only needs to be positive definite for vectors $v \in \mathbb{R}^n$ lying in the span of columns of $U$. Clearly, the solution to this problem is guaranteed to be a better minima than the solution obtained by setting negative eigen values to zero.

Essentially we are saying that eigen-values corresponding to those eigen-vectors of $X$ that are orthogonal to $U$ can be anything. And Eigen-values for those eigen-vectors of$X$ that lie in the span of $U$ must be positive.

So immediately we get the following procedure for solving this problem.

1. Do Eigen decomposition of $M$ to get $n$ eigen-vectors $q_i$
2. If $U^Tq_i \ne 0$ then modify the corresponding eigen-value $\lambda_i$ to $\max(0, \lambda_i)$, Otherwise the sign does not matter, we can leave as is.

This is guaranteed to be a feasible solution, and its guaranteed to be better than the vanilla algorithm outlined in the question.

Although this procedure is an improvement its not guaranteed to be minima of the original problem. To get a true minima some more thought is needed. I will update when I get a chance to think more about this.

Answer 2

Up to an orthogonal change of basis you may assume $U = \begin{bmatrix}I_d\\0\end{bmatrix}$. In this basis, the problem becomes $$ \min_{X_{11} \succeq 0} \left\|\begin{bmatrix}X_{11} & X_{12}\\ X_{12}^T & X_{22}\end{bmatrix} -\begin{bmatrix} M_{11} & M_{12}\\M_{12}^T & M_{22}\end{bmatrix} \right\|_F, $$ which clearly has solution $X_{12}=M_{12}$, $X_{22}=M_{22}$ and $X_{11} = M_{11}^*$ (where $M_{11}^*$ is defined as in your text, i.e., $M_{11}^*=Q\max(D,0)Q^{-1}$ from the eigendecomposition $M_{11}=QDQ^{-1}$).