Monday, June 15, 2015

Riemannian preconditioning for tensor and matrix completion - implementation(s) -

 
Bamdev just sent me the following: 
 
 Dear Igor,

I wish to share our recent technical report on "Riemannian preconditioning for tensor completion", available at http://arxiv.org/abs/1506.02159. The results are promising.


It works with the fixed-rank Tucker manifold by endowing it with a "preconditioned" Riemannian geometry. The preconditioned geometry results from exploiting the two fundamental structures of the completion problem, i.e.,
1) the quadratic structure of the cost function and
2) the non-uniqueness of Tucker decomposition.


The code is available at http://bamdevmishra.com/codes/tensorcompletion/. It is built on the Manopt toolbox for optimization on manifolds.
The work actually builds upon the earlier work on matrix completion "R3MC: A Riemannian three-factor algorithm for low-rank matrix completion", available at http://arxiv.org/abs/1306.2672. The code is at http://bamdevmishra.com/codes/r3mc/.


The general preconditioning idea is motivated in "Riemannian preconditioning", available at http://arxiv.org/abs/1405.6055


Regards,
Bamdev
Thanks Bamdev ! Here are the attendant papers:
 
Riemannian preconditioning for tensor completion by Hiroyuki Kasai, Bamdev Mishra
We propose a novel Riemannian preconditioning approach for the tensor completion problem with rank constraint. A Riemannian metric or inner product is proposed that exploits the least-squares structure of the cost function and takes into account the structured symmetry in Tucker decomposition. The specific metric allows to use the versatile framework of Riemannian optimization on quotient manifolds to develop a preconditioned nonlinear conjugate gradient algorithm for the problem. To this end, concrete matrix representations of various optimization-related ingredients are listed. Numerical comparisons suggest that our proposed algorithm robustly outperforms state-of-the-art algorithms across different problem instances encompassing various synthetic and real-world datasets.


R3MC: A Riemannian three-factor algorithm for low-rank matrix completion by B. Mishra, R. Sepulchre

We exploit the versatile framework of Riemannian optimization on quotient manifolds to develop R3MC, a nonlinear conjugate-gradient method for low-rank matrix completion. The underlying search space of fixed-rank matrices is endowed with a novel Riemannian metric that is tailored to the least-squares cost. Numerical comparisons suggest that R3MC robustly outperforms state-of-the-art algorithms across different problem instances, especially those that combine scarcely sampled and ill-conditioned data.
 

Riemannian preconditioning by Bamdev Mishra, Rodolphe Sepulchre
The paper exploits a basic connection between sequential quadratic programming and Riemannian gradient optimization to address the general question of selecting a metric in Riemannian optimization, in particular when the Riemannian structure is sought on a quotient manifold. The proposed method is shown to be particularly insightful and efficient in quadratic optimization with orthogonality and/or rank constraints, which covers most current applications of Riemannian optimization in matrix manifolds.
 
 
 
Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

No comments:

Printfriendly