Diagonal constraint on product of matrices

827 Views Asked by At

I am trying to solve the below optimization problem

\begin{equation*} \begin{aligned} & \underset{{A}, {B}, {\Lambda}}{\text{minimize }} & & \|X - AB\Lambda B^TA^T\|_F^2 \\ & \text{subject to} & & \Lambda~\text{and}~B\Lambda~B^T\text{are diagonal matrices}\\ \end{aligned} \end{equation*} where $X \in R^{n\times n}, A\in R^{n\times k_1}, B \in R^{k_1\times k_2}, \Lambda \in R^{k_2\times k_2}$, $X$ is known and $n > k_1 > k_2$. I am not sure how to put a constraint on $B$ and $\Lambda$ such that $B\Lambda B^T$ is a diagonal matrix. I know I can solve for all unknown using alternative minimization but I am not sure how to include the constraint.

Edit 1: Changed the optimization problem

1

There are 1 best solutions below

2
On BEST ANSWER

Let $S=AB\Lambda B^TA^T$ and $H=\frac12(X+X^T)$. Then the rank of $S$ is at most $k_2$ and \begin{align} \|X-S\|_F^2 &=\operatorname{tr}\left((X-S)^T(X-S)\right)\\ &=\operatorname{tr}(X^TX)-2\operatorname{tr}(X^TS)+\operatorname{tr}(S^TS)\\ &=\operatorname{tr}(X^TX)-2\operatorname{tr}(HS)+\operatorname{tr}(S^TS)\\ &=\operatorname{tr}(X^TX)-\operatorname{tr}(H^TH)+\|H-S\|_F^2. \end{align} It follows that the global minimiser $S$ is a best rank-$k_2$ approximation of $H$. That is, if $H=QDQ^T$ is an orthogonal diagonalisation where the diagonal entries of $D$ are arranged in the order of decreasing magnitude, and we partition $Q$ and $D$ as $\pmatrix{Q_1&Q_2}$ and $D_1\oplus D_2$, where both $Q_1$ and $D_1$ have $k_2$ columns each, then $S=Q_1D_1Q_1^T$ is a global minimiser. You may now pick any $A,B,\Lambda$ that satisfy your constraints such that $AB\Lambda B^TA^T$ is equal to $S$. E.g. you may simply pick $A=\pmatrix{Q_1&0},\ B=\pmatrix{I_{k_2}\\ 0}$ and $\Lambda=D_1$. The corresponding (minimum possible) objective function value is $\operatorname{tr}(X^TX)-\operatorname{tr}(H^TH)+\sum_{i=1}^{n-k_2}(D_2)_{ii}^2$.