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,\quad V^{T} V = I,\quad \mbox{diag}(\Sigma) \geq 0, \quad \mbox{rank}(U) = \mbox{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. Commented May 3, 2017 at 19:02
• Uwe Helmke, John B. Moore, Optimization and Dynamical Systems, 2nd edition, March 1996. Commented May 4, 2017 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$.