the connection between symmetric positive semidefinite problems (factory) and general low rank matrix problems (factory)

[lineya...@gmail.com]

Hi,

Recently there are a lot of works on low rank problems and I notice that some analysises for non-square matrices are based on the semidefinite lifting, as shown in the following papers.

Zheng, Qinqing, and John Lafferty. "Convergence analysis for rectangular matrix completion using Burer-Monteiro factorization and gradient descent."arXiv preprint arXiv:1605.07051 (2016).

Ge, Rong, Chi Jin, and Yi Zheng. "No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis." arXiv preprint arXiv:1704.00708 (2017). 

With matrix factorization approach, a low rank problem where rank(X)=k can be factorized as X=UV^T  can be transformed to a positive semidefinite problem with variable Z=WW^T and   W^T = [U^T, V^T]. I'm confused that in the view of optimization whether this reformulated problem is equivalent with (or better, worse than) directly solving the original problem, and why? Because if we can always do this, it seems unnecessary to develop algorithms on the general non-square low rank matrix problems. I'm looking forward for your reply.

Thank you a lot.

Kai

[Nicolas Boumal]

Hello Kai,

The answer to your question can depend a lot on what you want to do with that optimization problem.

If your aim is to solve and/or analyze your rectangular matrix problem through the prism of a convex relaxation in the set of positive semidefinite matrices, than the approach in W seems appropriate. If your intent is only to optimize for U and V (despite non-convexity, which turns out to be fine in many cases of interest), then the two approaches might be equivalent, although it will eventually depend on the algorithms you choose.

Best,

Nicolas

[lineya...@gmail.com]

Hi Nicolas,

So with algorithms based on matrix factorization, they might be equivalent in the view of solutions. But how about the computational cost with Riemannian conjugate gradient or Riemannian trust region algorithms for both approaches? Will the semidefinite listing bring extra computational overhead?

Thanks.

Kai

[Nicolas Boumal]

Hello Kai,

In general, I expect semidefinite programs to be more expensive to solve indeed, though here too it could depend on the size and conditioning of the problem. I suppose experimenting is the only way to know.

Best,
Nicolas