Solving for Optimal Linear Isometry

67 Views Asked by At

Updated:

Let $X,Y$ be matrices in $Mat_{d\times D}(\mathbb{R})$. and fix $\lambda >0$ How can I find a pair of matrices $A,B$ such that: $$ \min_{\underset{A \in Mat_{d\times d}(\mathbb{R}) \, A^{\top}A =I_d}{B \in Mat_{d\times D}(\mathbb{R})}}\|A(X-B) -Y\|_F + \lambda \|B\|_F $$ where $Mat_{d\times D}(\mathbb{R})$ is the set of $d\times D$ matrices with real-coefficients and $\|\cdot\|_F$ is the Frobenius norm.

How can we solve for $A$? I looked it up, and by a comment below, if we additionally constrain $B=0$ then the solution is $$ A = U^{\top}V \mbox{ where $U\Sigma V^{\top}$ is the SVD of A}. $$ But what about in general?

1

There are 1 best solutions below

1
On BEST ANSWER

For typing convenience, use a colon as a product notation for the trace, i.e. $$A:B = {\rm Tr}(A^TB) = {\rm Tr}(B^TA) = B:A$$ Then define the matrix $Z=X-B\,$ and assume for the moment that $B$, and therefore $Z$, are fixed.

Expand the objective function as $$\eqalign{ \|AZ-Y\|_F^2 &= (AZ-Y):(AZ-Y) \\ &= AZ:AZ + Y:Y - 2Y:AZ \\ &= (A^TA:ZZ^T + Y:Y) - 2YZ^T:A &\qquad\big\{ A^TA=I\big\} \\ &= (I:ZZ^T + Y:Y) - UDV^T:A &\qquad\big\{ {\rm SVD\,factorization}\big\} \\ &= \Big(\|Z\|^2_F+\|Y\|^2_F\Big) - {\rm Tr}(D\,U^TAV) \\ }$$ This leads to the standard Procrustes solution method: $$\eqalign{ \min_A\,\|AZ-Y\|_F^2 \quad\implies\quad \max_A\,{\rm Tr}(D\,U^TAV) \quad\implies\quad A=UV^T }$$ However, $B$ is not fixed so we're free to choose it to minimize the objective function.

Setting $B=X-Y\;$ yields $$\eqalign{ Z=Y,\quad A=I \quad\implies\quad \|AZ-Y\|_F^2=0 }$$ which is the global minimum for the Frobenius norm.