# Solution to the optimization problem in “Blessing of Dimensionality High … the face verification”

I am reading the work "Blessing of Dimensionality High dimensional feature and its efficient compression for the face verification" CVPR 2013. One of the key contributes is the authors propose a new so called "rotated sparse regression" method for the dimension reduction. However, I don't know how to get the closed form solution for following optimization problem. The details are not given in the paper. Could someone give me a hint to derive the following closed form in the following

• @StefanoM, I think he means, "how do you prove this is the minimum of of the constrained problem above?" – Bill Barth May 22 '15 at 14:21
• @BillBarth You are right, sorry: I deleted the negative comment. May be the question should be edited to clarify? "I don't know how to get the closed form solution..." hints to "how to compute." – Stefano M May 22 '15 at 14:24
• You should be able to work this out by differentiating the upper expression w.r.t. $R$, setting it equal to zero, and solving. At some point, you will want to apply the SVD expression they assume and the constraint. – Bill Barth May 22 '15 at 18:03

There's a well known problem called the orthogonal Procrustes problem,

$\min_{Q} \| AQ-B \|_{F}$

subject to the constraint

$Q^{T}Q=I.$

Note that the norm in the objective function is the Frobenius norm rather than the matrix 2-norm.

For this problem, the solution is

$Q=UV^{T}$

where $A^{T}B$ has the SVD

$A^{T}B=U\Sigma V^{T}$.

This solution to the Procrustes problem is derived in lots of places. See for example the Wikipedia page here:

http://en.wikipedia.org/wiki/Orthogonal_Procrustes_problem

If your problem had the objective $\min \| R^{T}Y-B^{T}X \|_{F}$ rather than $\| R^{T}Y-B^{T}X \|_{2}^{2}$, then the problem could be rewritten as a Procrustes problem by transposing inside the norm,

$\min \| Y^{T}R - X^{T}B \|_{F}$

subject to

$R^{T}R=I$.

The solution would be

$R=UV^{T}$

where $YX^{T}B$ has the singular value decomposition

$YX^{T}B=U\Sigma V^{T}$.

This matches up exactly with the solution given in the paper that you've quoted.

I don't believe that minimizing the 2-norm is equivalent to minimizing the Frobenius norm. It seems to me that the authors of the paper you cite may have confused the Frobenius norm and the 2-norm.

Added after I finally got my hands on Watson's 1993 paper...

See

G. A. Watson. Solving Generalizations of Orthogonal Procrustes Problems. In Contributions in Numerical Mathematics, World Scientific Series in Applicable Analysis, World Scientifc Publishers, 1993.

The classical solution using the SVD is optimal with respect to the 2-norm only if the matrices are square ($m=n$), and the $A$ matrix is the identity- that is, we're minimizing $\min \| Q-B \|_{2}$.

Otherwise, Watson offers an iterative algorithm that requires the solution of a quadratic programming problem at each iteration.

• I think the simpler form of the Procrustes problem should work the same in the spectral norm; could you maybe have a look at my proof in the other answer? Although you may be right that the more general form with two matrices $\|AQ-B\|_2$ doesn't work out... – cfh May 23 '15 at 20:18
• See the following reference (Google will show you the first few pages and I've got ILL working on getting a copy...) The $UV^{T}$ formula doesn't work in general according to the abstract although it does in the special case of $\min \| M-Q \|_{2}$. I think you'll find sufficient conditions in Watson's paper: Watson, G. A. "Solving generalizations of orthogonal Procrustes problems." World Scientific Series in Applicable Analysis 2 (1993): 413-426. – Brian Borchers May 23 '15 at 20:39
• A different citation for what appears to be a related paper: Watson, G A. "The Solution of Orthogonal Procrustes Problems for a Family of Orthogonally Invariant Norms." Advances in Computational Mathematics. 2.4 (1994): 393-405. – Brian Borchers May 23 '15 at 20:44
• From my reading of the article cited by the original poster, it appears that they're interested in the Frobenius norm anyway (the columns of the $Y$ matrix are feature vectors that are supposed to be rotated to match columns of $B^{T}X$. – Brian Borchers May 23 '15 at 21:56
• A lot of computer scientists mistakenly call the frobenius norm the "2-norm". It's so prevalent, I have started to suspect that its actually just a different naming convention in the field. – Nick Alger May 24 '15 at 13:56

I couldn't find anything on the Procrustes problem in the spectral norm online, but I had a feeling that the same result as in the Frobenius norm should hold, so I worked something out.

Let's say we're given a matrix $M$ and want to find an orthogonal matrix $Q$ which minimizes $$\min_{Q^T Q=I} \| M - Q \|_2.$$ We take the SVD of $M$, i.e., $$M = U \Sigma V^T.$$ In particular, we have normed singular vectors $u_j,v_j$ with $M v_j = \sigma_j u_j$ and hence $\|M v_j\| = \sigma_j$.

For any such orthogonal matrix $Q$ and any vector $v$ with $\|v\|=1$, we have $$\| M - Q \|_2 \ge \| Mv - Qv \| \ge \Big| \| Mv \| - \| Qv\|\Big| = \Big| \| Mv \| - 1 \Big|,$$ and by inserting the singular vectors $v_j$, we obtain $$\| M - Q \|_2 \ge \max_j | \sigma_j - 1 |.$$ On the other hand, the special choice $Q = UV^T$ leads to $$\| M - Q \|_2 = \| U (\Sigma - I) V^T \|_2 = \| \Sigma - I \|_2 = \max_j |\sigma_j - 1|$$ and is therefore the best approximation of $M$ in the spectral norm as well.

However, this does not hold for the generalization to the more general problem $\| A Q - B\|_2 \to \min$ according to the paper cited by Brian Borcher above: Watson, G. A. "Solving generalizations of orthogonal Procrustes problems." World Scientific Series in Applicable Analysis 2 (1993): 413-426