Orthogonality constraints when formulating SVD as optimization problem

I am working on a project that requires me to formulate the singular value decomposition (SVD) as an optimization problem. In order to do this I need to require that $U$ and $V$ in $A =USV^T$ are orthogonal. Thus my problem looks something like this: $$\arg\min_{U,\Sigma,V}\left\Vert A-U\Sigma V^{T}\right\Vert _{F}^{2}$$ Subject to $$U^{T}U=I,\ V^{T}V=I,\ diag(\Sigma)\geq0,\ rank(U)=rank(V)=n$$

(As a side note I am not too worried about enforcing the size and rank of U and V, nor the sign of the singular values.)

I have no idea how to handle the orthogonality constraints. I am new to optimization. I have seen the paper A feasible method for optimization with orthogonality constraints. It says that orthogonality constraints are not convex, however someone I am working with assures me that the above problem is nonlinear convex. I could attempt to use the transformation mentioned in the paper, but I have seen similar problems with orthogonality constraints that don't mention a Cayley transform, which makes me wonder if there are other methods.

Here is what I would like to figure out:

• Is there a general way to handle the constraints $U^TU = I$ or even $||u_i|| = 1$?
• Can I formulate the orthogonality constraints as bilinear constraints?
• Is there a known formulation of the SVD as an optimization problem? (along with solution algorithm ideally)

As of now I may try to solve for PCA as an optimization problem and use that to find the SVD of my centered dataset. I would prefer however to be able to find the SVD of the original dataset.

• As expressed, it is certainly not a convex problem. If $U,V$ satisfy the constraint then so does $-U,-V$ but clearly their average does not. – copper.hat May 3 '17 at 19:02
• Uwe Helmke, John B. Moore, Optimization and Dynamical Systems, 2nd edition, March 1996. – Rodrigo de Azevedo May 4 '17 at 12:07

The easiest example to consider is solving the following eigenvalue problem using the Rayleigh quotient (only numerator is important): $$\max_{x\in \mathbb{R}^n} x^TAx$$ subject to: $$||x||=1$$ The maximum is the largest eigenvalue of A (it must be diagonalizable of course), and the value of $x$ that gives the maximum is the associated eigenvector. You can think of the unit length constraint on the vector $x$ as forcing it to lie on the surface of an (n-1)-sphere. This is easy to picture mentally if n=2 or 3.
In my question above the constraint $U^TU=I$ is equivalent to solving along a Grassmann manifold (or Stiefel manifold I believe) for the variable $U$. The same goes for $V$.