Manopt 3.0 released - implementation -

Nicolas just sent me the following:

Dear Igor,

Bamdev (cc) and I just released Manopt 3.0, our Matlab toolbox for optimization on manifolds:

http://www.manopt.org/downloads.html 

We would be delighted if you could announce this major release on your blog once again.

Manopt is a toolbox for optimization on manifolds, with major applications in machine learning and computer vision (low rank constraints, orthogonal matrices, ...). Of course, Manopt can also optimize over linear spaces (and it's quite good at it).

This is non-convex optimization. Yet, more and more papers show that certain classes of non-convex problems on manifolds can be solved to global optimality with local algorithms such as the ones implemented in Manopt. These tools are also routinely used to refine solutions obtained by convex or spectral relaxations, with excellent results.

The toolbox is user friendly, requiring little knowledge about manifolds to get started. See our tutorial and the many examples in the release:

http://www.manopt.org/tutorial.html 

Best,

Nicolas

 
 Sure Nicolas ! As a side note, Manopt even has a tag on Nuit Blanche and it is manopt.

 Here are the changes from Manopt 2.0

 

• Manopt 3.0, packaged November 12, 2016.
• Code moved to GitHub! Now accepting pull requests, and accelerating distribution of patches.
• Bugs caught
• Logic bug in linesearch: lsmem handling corrected thanks to Wen Huang. The default line-search algorithm for steepest descent should now be much faster.
• Logic bug in getGradient when using problem.grad with a different number of inputs compared to problem.cost.
• Corrected logic in plotting step of example low_rank_dist_completion
• obliquefactory, in transposed mode, had an incorrect M.log
• Modifications to core engine
• Added capability to obtain a partial gradient (Euclidean or Riemannian) of a cost function by specifying problem.partialgrad or problem.partialegrad coupled with problem.ncostterms. This is an important step to simplify the future addition of stochastic gradient methods. Use cases are: if problem.cost is expressed as a sum of problem.ncostterms terms, then problem.partialgrad accepts a point x and an index set I so that only the gradient with respect to terms indexed in I is computed and returned.
• Added possibility to define problem.approxgrad, to provide an approximation of the gradient. This can be populated with a generic gradient approximation based on finite differences via approxgradientFD. Solvers do this by default if they need a gradient and none is given. This feature is slow, but may be useful for prototyping. It is slow because Manopt generates an orthonormal basis of the tangent space, and compute a finite difference approximation of the directional derivative along each basis vector to get an approximate gradient (see also next item and new example thomson_problem.)
• getGradient now knows how to compute the gradient if the directional derivatives are accessible. This involves generating an orthonormal basis of the tangent space at the current point, then evaluating the directional derivative along each basis vector and taking the appropriate linear combination. This is very slow, especially for high dimensional manifolds.
• New tools
• lincomb for a generic way of computing a long linear combination of tangent vectors.
• grammatrix to compute the Gram matrix of a collection of tangent vectors.
• orthogonalize to orthogonalize a basis of tangent vectors.
• tangentorthobasis to obtain a random orthonormal basis of a tangent space, generically.
• smallestinconvexhull to compute the smallest tangent vector in the convex hull of a given collection of tangent vectors.
• hessianmatrix to get a matrix representing the Hessian at a point in an orthonormal tangent basis.
• checkretraction allows, for manifolds which have a correct exponential implemented, to verify the order of agreement between the retraction and the exponential, in order to determine numerically if the retraction is first- or second-order.
• New examples
• elliptope_SDP solves SDP's over positive semidefinite matrices with diagonal of 1's. This should run faster than the Max-Cut example for quite a few things.
• elliptope_SDP_complex, same as above for complex matrices. This solves the SDP which appears in PhaseCut and phase synchronization, for example.
• thomson_problem to illustrate the new features that allow to not specify the gradient of the cost (slow, but good for prototyping.)
• New geometries
• skewsymmetricfactory for skew-symmetric matrices (Euclidean geometry
• obliquecomplexfactory, to work with complex matrices whose columns (or rows) all have unit norm
• Modifications to previous behavior
• symfixedrankYYcomplexfactory now has a Riemannian metric matching that of euclideanfactory (it was scaled down by 2 as compared to previous Manopt versions.) This makes it easier to switch between those two geometries. Relevant changes propagated to radio_interferometric_calibration.
• hessianextreme now returns the info structure returned by the internal solver call. The helper tool tangentspherefactory now incorporates extra projections to ensure the vector returned by hessianextreme is indeed a tangent vector (former version could suffer from numerical drift.)
• At the end of generalized_eigenvalue_computation, added a rotation of Xsol to match the definition of generalized eigenvectors (the eigenvalues were fine.)
• Numerous minor improvements; highlights:
• rotationsfactory now has a function M.retr2 which is a second-order retraction.
• spherefactory and related sphere geometries now have a distance function M.dist which is orders of magnitude more accurate for close-by points.
• neldermead now respects options.verbosity less than 2.
• plotprofile / surfprofile have now mostly optional inputs, making them easier to call for a quick glimpse at the cost function.

 
 
 

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page 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.

Pymanopt: A Python Toolbox for Optimization on Manifolds using Automatic Differentiation

We have covered Manopt before several times ( tag Manopt). It now comes to Python. From the paper:

Further successful applications of optimization on manifolds include matrix completion tasks (Vandereycken, 2013; Boumal and Absil, 2015), robust PCA (Podosinnikova et al., 2014), dimension reduction for independent component analysis (ICA) (Theis et al., 2009), kernel ICA (Shen et al., 2007) and similarity learning (Shalit et al., 2012).
Many more applications to machine learning and other elds exist. While a full survey on the usefulness of these methods is well beyond the scope of this manuscript, we highlight that at the time of writing, a search for the term \manifold optimization" on the IEEE Xplore Digital Library lists 1065 results; the Manopt toolbox itself is referenced in 90 papers indexed by Google Scholar.

It looks like that at the time of this writing, it is more like 126 times that the Manopt toolbow has been referenced in Google Scholar.

Pymanopt: A Python Toolbox for Optimization on Manifolds using Automatic Differentiation by  James Townsend, Niklas Koep, Sebastian Weichwald

Optimization on manifolds is a class of methods for optimization of an objective function, subject to constraints which are smooth, in the sense that the set of points which satisfy the constraints admits the structure of a differentiable manifold. While many optimization problems are of the described form, technicalities of differential geometry and the laborious calculation of derivatives pose a significant barrier for experimenting with these methods.
We introduce Pymanopt (available at this https URL), a toolbox for optimization on manifolds, implemented in Python, that---similarly to the Manopt Matlab toolbox---implements several manifold geometries and optimization algorithms. Moreover, we lower the barriers to users further by using automated differentiation for calculating derivative information, saving users time and saving them from potential calculation and implementation errors.

 
 The implementation is here: https://pymanopt.github.io/

 

h/t Nando. 
 
 

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page 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.

Riemannian stochastic variance reduced gradient on Grassmann manifold - implementation -

 

 

 

Bamdev just sent me the following:

 

Dear Igor,

I wish to share our recent technical report on "Riemannian stochastic variance reduced gradient on Grassmann manifold", available at http://arxiv.org/abs/1605.07367. In this paper, we extend the Euclidean SVRG algorithm to compact Riemannian manifolds. The results are encouraging.

Additionally, the codes are available at https://bamdevmishra.com/codes/rsvrg/. We also provide a template file, Riemannian_svrg.m, that is compatible with the Manopt toolbox [1].


Regards,
Bamdev

[1] http://manopt.org. 

Thanks Bamdev ! Here is the paper: Riemannian stochastic variance reduced gradient on Grassmann manifold by Hiroyuki Kasai, Hiroyuki Sato, Bamdev Mishra

Stochastic variance reduction algorithms have recently become popular for minimizing the average of a large, but finite, number of loss functions. In this paper, we propose a novel Riemannian extension of the Euclidean stochastic variance reduced gradient algorithm (R-SVRG) to a compact manifold search space. To this end, we show the developments on the Grassmann manifold. The key challenges of averaging, addition, and subtraction of multiple gradients are addressed with notions like logarithm mapping and parallel translation of vectors on the Grassmann manifold. We present a global convergence analysis of the proposed algorithm with decay step-sizes and a local convergence rate analysis under fixed step-size with some natural assumptions. The proposed algorithm is applied on a number of problems on the Grassmann manifold like principal components analysis, low-rank matrix completion, and the Karcher mean computation. In all these cases, the proposed algorithm outperforms the standard Riemannian stochastic gradient descent algorithm.

 
 
 

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page 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.

Manopt 2.0: A Matlab tool­box for opti­mization on manifolds - implementation -

Nicolas Boumal just let me know of the following:

Dear Igor,

Bamdev (cc) and I develop Manopt, a Matlab toolbox for optimization on manifolds.

You featured a nice post about it on Nuit Blanche on May 28, 2013:

http://nuit-blanche.blogspot.fr/2013/05/manopt-matlab-toolbox-for-optimization.html

Over the last two years, the toolbox has improved vastly, in part thanks to our great contributors, and we just released Manopt 2.0 yesterday: 

http://www.manopt.org/downloads.html

http://www.manopt.org/about.html#contributors

We would be delighted if you could announce this major release on your blog once again.

Manopt is a toolbox for optimization on manifolds, that is, on smooth nonlinear spaces. This is ideal to handle rank constraints and orthogonality constraints, to name a few, with major applications in large-scale machine learning, computer vision, numerical linear algebra and scientific computing. Generically, it is an excellent paradigm to handle symmetry and invariance in optimization. Of course, Manopt can also optimize over linear spaces (and it's quite good at it). It is also a powerful way to refine ballpark estimates obtained from relaxations.

The toolbox is user friendly, requiring little knowledge about manifolds to get started. See our tutorial and the many examples in the release: 

http://www.manopt.org/tutorial.html

For a brief overview of what optimization on manifolds is about, this blog post may be a good start:

https://afonsobandeira.wordpress.com/2015/03/16/optimizing-in-smooth-waters-optimization-on-manifolds/

We hope you may find this to be of interest for Nuit Blanche's readership.

Thank you for your time,

Nicolas

Sure thing Nicolas and Bamdev !

From the About page:

Things users do with Manopt

We see a growing number of papers in various disciplines where researchers use Manopt. A list is available on Google Scholar. We single out a few projects we think illustrate some of the flexibility of the toolbox:

• Artiom Kovnatsky, Klaus Glashoff and Michael M. Bronstein proposed MADMM: a generic algorithm for non-smooth optimization on manifolds. This is essentially ADMM, where one of the steps is smooth optimization on a manifold ; that step is performed using Manopt.
• Reshad Hosseini and Suvrit Sra released a paper entitled Manifold Optimization for Gaussian Mixture Models. They address the important problem of estimating the distribution of data, when it is assumed to be sampled from a mixture (linear combination) of Gaussian distributions. See their MixEst project page for code and more. The same authors also developed the Geometric Optimization Toolbox (GOPT), aimed at optimization over the manifold of positive definite matrices. This includes a Riemannian BFGS algorithm.
• Vris Yuen-Lam Cheung, Dmitriy Drusvyatskiy, Nathan Krislock and Henry Wolkowicz consider a sensor network localization problem. They propose a smart way of obtaining a cheap initial guess, then refine this ballpark estimate to high accuracy with Manopt. They find that neither works very well without the other. The general idea of combining smart spectral or convex formulations to obtain rough (but controllable) estimates, then refining these using Manopt, is successful in many applications.

but also 

Related software

• GenRTR is the Generic Riemannian Trust-Region package for Matlab (it is included in a slightly modified form in Manopt) ;
• GROPT is a Riemannian optimization package written in C++ (with mex interface to Matlab), by Wen Huang and Kyle Gallivan ;
• GOPT is designed for optimization over positive definite matrices.
• SGMIN performs Stiefel-Grassmann optimization ;
• GrassmannOptim is an R-package for optimization on the Grassmann manifold ;
• Optman hosts a collection of algorithms from Rice University for optimization with orthogonality constraints ;
• Traian Abrudan has code for optimization under unitary matrix constraints ;
• LORM is a C++ toolbox for global optimization of polynomials on the sphere and the special orthogonal group.
• Your code? Let us know!

 

  Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page 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.

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.

A Riemannian approach to low-rank algebraic Riccati equations - implementation -

Somehow related to neutron transport theory and a different kind of matrix factorization, here is: A Riemannian approach to low-rank algebraic Riccati equations by Bamdev Mishra, B. Vandereycken

We propose a Riemannian optimization approach for computing low-rank solutions of the algebraic Riccati equation. The scheme alternates between fixed-rank optimization and rank-one updates. The fixed-rank optimization is on the set of fixed-rank symmetric positive definite matrices which is endowed with a particular Riemannian metric (and geometry) that is tuned to the structure of the objective function. We specifically discuss the implementation of a Riemannian trust-region algorithm that is potentially scalable to large-scale problems. The rank-one update is based on a descent direction that ensures a monotonic decrease of the cost function. Preliminary numerical results on standard small-scale benchmarks show that we obtain solutions to the Riccati equation at lower ranks than the standard approaches.

from the code page of Bamdev Mishra

We solve the equation $A^TX + XA + X BB^T X = C^TC$ for X on the low rank manifold of symmetric and positive definite matrices, where A is large and sparse, B is a tall matrix, and C is a fat matrix. For $B = 0$, this boils down to the Lyapunov equation.

The code has been tuned for large scale problems. Computationally, the numerical bottleneck involes solving the linear system $Px = b$, where P is a sparsely-structured matrix.

In the present code, $Px = b$ for smaller to moderate size problems (about 10 000 x 10 000) is solved with the backslash operator of Matlab without any tuning. For larger size matrices, we employ the Matlab's built-in iterative pcg solver without any tuning, which may not be efficient for all problems. Specific problems call for specific solvers! If you are interestd in a particular setup and have a solver, then do look for the function "use_iterative_solver" in the file "Main_files/Riemannian_lowrank_riccati.m" and modify it accordingly.

The code is built on the Manopt platform. Feel free to contact me on any issue.

It will be added to the Advanced Matrix Factorization Jungle page.

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.

Manopt: A Matlab tool­box for opti­mization on manifolds - implementation -

From the previous entry, but I wanted to dedicate an entry just that implementation, Bamdev Mishra also mentions the release of Manopt. Please note the tutorial page and a forum:

Manopt toolbox is officially released

Manopt  is a Matlab tool­box for opti­mization on manifolds. Op­ti­miza­tion on man­i­folds is a pow­er­ful par­a­digm to ad­dress non­lin­ear op­ti­miza­tion prob­lems. With Ma­nopt, it is easy to deal with var­i­ous types of con­straints that arise nat­u­rally in ap­pli­ca­tions, such as or­tho­nor­mal­ity or low rank. It comes with a large library of manifolds and ready-to-use Riemannian optimization algorithms. It is well documented and includes diagnostics tools to help you get started quickly and make sure you make no mistakes along the way. It is designed to provide great flexibility in describing your cost function and incorporates an optional caching system for more efficiency.

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.

qGeomMC: A Quotient Geometric approach to low-rank Matrix Completion - implementation -

While searching for something else, I stumbled upon Bamdev Mishra's page and found this implementation featured in A Riemannian geometry for low-rank matrix completion by Bamdev Mishra, K. Adithya Apuroop, Rodolphe Sepulchre

We propose a new Riemannian geometry for fixed-rank matrices that is specifically tailored to the low-rank matrix completion problem. Exploiting the degree of freedom of a quotient space, we tune the metric on our search space to the particular least square cost function. At one level, it illustrates in a novel way how to exploit the versatile framework of optimization on quotient manifold. At another level, our algorithm can be considered as an improved version of LMaFit, the state-of-the-art Gauss-Seidel algorithm. We develop necessary tools needed to perform both first-order and second-order optimization. In particular, we propose gradient descent schemes (steepest descent and conjugate gradient) and trust-region algorithms. We also show that, thanks to the simplicity of the cost function, it is numerically cheap to perform an exact linesearch given a search direction, which makes our algorithms competitive with the state-of-the-art on standard low-rank matrix completion instances.

That implementation is available from this page:  qGeomMC: A Quotient Geometric approach to low-rank Matrix Completion

This package contains a MATLAB implementation of algorithms for the low-rank matrix completion problem. The present version includes gradient descent and conjugate gradient algorithms based on the fixed-rank geometry proposed in the techreport [arXiv:1211.1550]......

Bamdev Mishra also mentions the release of two other implementations:

 Manopt toolbox is officially released...

Manopt comes with a large library of manifolds and ready-to-use Riemannian optimization algorithms. It is well documented and includes diagnostics tools to help you get started quickly and make sure you make no mistakes along the way. It is designed to provide great flexibility in describing your cost function and incorporates an optional caching system for more efficiency.

 Updated TraceNorm code to handle large scale matrices

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.