Download The current version is 6.0 and was packaged on May 19, 2020. The file is about 400 Kb.
GitHub Latest code available on GitHub at all times, and accepting pull requests.
Go to the tutorial page for the simple installation instructions and a first example.
It helps us to know our users: please follow this link to hear about updates. Thanks!
Do you use Manopt for teaching? Please get in touch! We'd love to know about this and get feedback.
- Manopt 6.0, packaged May 19, 2020
- Modifications to core engine
- Made it possible for egrad2rgrad and ehess2rhess in a factory-produced manifold to take (storedb, key) as input. The purpose is to allow some automatic caching of redundant computations in ehess2rhess wrt egrad2rgrad. If they do, then they should accept to be called without (storedb, key), so as not to generate errors with powermanifold and productmanifold, which cannot handle this.
- New geometries
- New tools
- Added gradient descent and nonlinear conjugate gradient subproblem solvers for Riemannian ARC.
- Improved numerical stability of Lanczos subproblem solver for ARC.
- Changed default parameters of ARC and added checks to react if subproblem solver fails.
- Added preconditioner support to stochasticgradient solver.
- Other changes
- Fix to productmanifold so that it defines a method for the product only if that method is available for each element.
- Added a new retraction to generalized Stiefel manifold, and made it the default retraction.
- Minor changes to multinomialfactory and also added exp, log and dist functions.
- For the manifold fixedrankembeddedfactory: added tools triplet2matrix and matrix2triplet, improved numerical behavior of the retraction for ill-conditioned tangent vectors and vec/mat replaced with lower dimensional isometries, which speed up use of hessianspectrum with that factory considerably.
- Changes to grassmannfactory: tweaks to ehess2rhess for numerical accuracy and added pairmean.
- Added exp, log and dist in the factory symfixedrankYYfactory.
- Differentials of matrix functions (dexpm, dlogm, dsqrtm, dfunm) now also return the matrix function evaluation as a by-product.
- The tool checkdiff (hence also checkgradient) now checks that the cost function is real.
- The tool checkhessian now checks that the Hessian is a linear operator.
- Added some extra checks to checkmanifold, notably to test vec/mat and dim; and improved test of exp/log/dist.
- Refactored a number of retractions to use new tool qr_unique.
- Several improvements to multinomialdoublystochasticfactory.
- The tool tangentspacefactory should now work with factories involving a non-identity tangent2ambient.
- Bug fix: memory usage could increase with inner iterations of tCG inside trustregions when using finite difference approximation of the Hessian. This is no longer the case.
- Generally improved comments in several files.
- Manopt 5.0, packaged September 10, 2018
- New solvers
- ARC: adaptive regularization by cubics, arc, as an alternative to trustregions.
- Modifications to core engine
- New counters system: especially useful to keep track of cost/grad/hess calls, and also of other important computations inside of (and possibly shared among) those. See incrementcounter and statscounter and the example using_counters. As also shown in that example, the
problem.stopfun handle for stopping criteria can access the counters, making it possible to stop for more sophisticated reasons than before.
- The value of the cost function is now always cached. This leads to significant speed-ups in algorithms which use a line-search that evaluates the cost function (steepestdescent, conjugategradient, barzilaiborwein, rlbfgs included.)
- The Riemannian gradient and Euclidean gradient are now cached by default. This is made practical by the new remove() functionalities of StoreDB (see below). This should be particularly useful for algorithms which use finite difference approximations of the Hessian, and when the user supplies a Euclidean Hessian (which, to be converted to Riemannian Hessian, requires the Euclidean gradient). This caching happens regardless of the user's own caching efforts, which should make the overall system easier to understand, as compared to previous versions of Manopt.
- Core changes to StoreDB. Essentially two changes: (1) purge() now purges based on latest access time (access = read or write) rather than latest write time. (2) Added functions remove() and removefirstifdifferent(), which makes it possible for solvers and line-search algorithms to tell the StoreDB when a certain store is no longer relevant. For solvers that use the new remove() capabilities, purge() and storedepth now have very little importance. Furthermore, access is now more protected, with warnings issued if improper keys are accessed; this should make it easier to debug new solvers, and it already makes it possible to cache far fewer points. This rationalizes the choice of caching more things for points that matter (including cost and gradient). Line-search algorithms and all important solvers now use this system.
- Added support for GPU. The following manifolds can now manipulate points and tangent vectors directly on the GPU, sometimes leading to huge speed-ups: spherefactory, complexcirclefactory, stiefelfactory, grassmannfactory; see the new example using_gpu.
- New tools
- orthogonalizetwice runs the rewritten orthogonalize tool twice for better accuracy when orthonormalizing an ill-conditioned basis of tangent vectors.
- lyapunov_symmetric and lyapunov_symmetric_eig: solvers for Lyapunov equation $AX + XA = C$ with symmetric (or Hermitian) matrix $A$; acts as a pseudo-inverse. sylvester_nochecks: Matlab's sylvester solver without input checks (much faster for small matrices); These are now used everywhere in Manopt to remove dependency on lyap, which is a tool from the Control Toolbox.
- stopifdeletedfile and stopifclosedfigure: interactive stopping criteria that allow to stop a solver at any point, and let it finish gracefully and continue executing the rest of the code (also for execution on a distant server without GUI.)
- checkmanifold: began a new tool to run a collection of tests on manifold structures returned by factories; this is an early version to collect ideas as they come.
- New geometries
- Bug fixes
- Fixed M.retr2 (second-order retraction) in rotationsfactory for k > 1.
- Other changes
- Installation instructions and importmanopt now include savepath
- orthogonalize tool is now a modified Gram-Schmidt algorithm, which is more stable than the previous code
- strict_inc_func in rlbfgs solver changed following recommendations of Wen Huang
- More heads up messages regarding the use of M.tangent2ambient with some manifolds
- tCG solver for trustregions inner problems is now more stable (numerically) for fine convergence steps
- Added inverse retraction for grassmannfactory, stiefelfactory (both QR and polar retractions, both of which are now available), spherefactory, obliquefactory, rotationsfactory (both QR and polar) and complexcirclefactory.
- neldermead solver now uses retraction instead of exponential.
- If the exponential is not implemented for a manifold, M.exp is now no longer defined. It used to be that M.exp would issue a warning, then return the result of M.retr. But this causes a deluge of warnings in functions such as checkhessian. Now, instead, such tools check if M.exp is defined; if not, they use M.retr and issue a single message to inform the user of the consequences. If your personal code uses M.exp() without checking for manifolds that didn't have a proper implementation, you may want to check if this update breaks that part. It should be an easy fix.
- Many small improvements here and there...
- Manopt 4.0, packaged September 9, 2017
- New solvers
- Limited-memory BFGS, rlbfgs: a Riemannian version of the quasi-Newton solver, implemented by Changshuo Liu based on work by Wen Huang et al.
- barzilaiborwein: a gradient method with step-size selection based on a Barzilai-Borwein heuristic and line-search, contributed by Margherita Porcelli and Bruno Iannazzo.
- stochasticgradient: stochastic gradient algorithm on manifolds, together with its step-size selection algorithm stepsize_sg and a new example: PCA_stochastic.
- New tools
- tangent2vec: given a tangent vector and an orthogonal basis on the corresponding tangent space, returns the coordinates of the vector in that basis.
- criticalpointfinder: allows to find critical points of an optimization problem (useful to study saddle points of a non-convex problem for example.)
- New geometries
- realphasefactory: to optimize over vectors with unit-modulus complex entries (phases) with symmetries such that they could be the phases of the DFT (fft) of a real vector.
- Modifications to core engine
- Added the capacity to provide a subgradient in a problem description, and to call for it in a solver. This, together with the tool smallestinconvexhull, is an important step toward integrating nonsmooth solvers in Manopt. See canGetSubgradient and getSubgradient. Define with problem.subgrad(x, tol), where x is a point on a manifold problem.M and tol (nonnegative) is a tolerance in computing the subgradient (0 by default).
- Bug fixes
- tangentspacefactory now has correct tangent, egrad2rgrad and ehess2rhess tools, including projections (thanks to a comment by Jesus Briales on the forum.)
- For Euclidean manifolds, M.tangent functions were changed from identity to M.proj.
- Smaller things
- sympositivedefinitefactory now has a cheaper yet second-order retraction, as suggested by Wen Huang.
- euclideancomplexfactory now also handles multidimensional arrays, just like its real counterpart.
- smallestinconvexhull tool now accepts a tolerance as optional input.
- Further improved accuracy of distance function computations in all sphere / oblique manifolds with asin function instead of acos without branching, following discussions with Bruno Iannazzo and P.-A. Absil.
- Two new options for linesearch_hint: allows to disable backtracking and allows to disable forcing of a non-increasing cost.
- fixedrankembeddedfactory now has an orthographic retraction provided by Teng Zhang as M.retr_ortho.
- Many, many smaller improvements to code and documentation
- 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 sample so that only the gradient with respect to terms indexed in sample 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 < 2.
- plotprofile / surfprofile have now mostly optional inputs, making them easier to call for a quick glimpse at the cost function.
- Manopt 2.0, packaged July 6, 2015.
- Revamped the internal hashing system used for caching: Manopt no longer uses hashing, which leads to speed-ups and cleaner internal code. Solvers need to be adapted consequently, to use the StoreDB class.
- The caching system now offers a shared memory, which can be accessed and modified at all points. This can notably be used to count function evaluations, or to produce Hessian approximations which require previous iterations memory (such as BFGS for example).
- Because of the new class StoreDB, Octave compatibility is unfortunately compromised until Octave supports Matlab's classdef object oriented programming.
- New geometries:
- spherecomplexfactory: added ehess2rhess.
- complexcirclefactory: distance function corrected.
- Contributions more explicitly acknowledged in some files, notably via BibTex entries.
- hessianspectrum: output eigenvalues now sorted, and the square root of the preconditioner, if available, must now be given through problem.sqrtprecon, not as an additional input. An option now allows to ask for the Hessian spectrum or the preconditioned Hessian spectrum, explicitly.
- New management of Hessian approximations and preconditioners. The file hessianapproxFD encapsulates Manopt's standard approximation, with access to options. A first generic preconditioner allows solving linear systems involving the Hessian (for Newton-type methods): preconhessiansolve.
- Line-search algorithms now work with StoreDB, and as a result have a simplified calling pattern. There is also a new one: linesearch_decrease.
- New tools:
manoptsolve, to automatically call an appropriate solver (or a dynamically chosen solver) on a problem structure.
statsfunhelper, to ease the use of
options.statsfun, which allows recording custom statistics at each iteration during optimization. See the tutorial.
hessianextreme, to compute minimal and maximal eigenvectors and eigenvalues of the Hessian of a cost function.
surfprofile, to complement
plotprofile: used to plot a cost function restricted to a 1D or 2D subspace of a tangent space.
tangentspacefactory, to obtain a manifold representation of the unit sphere on the tangent space to a manifold at a given point, or a representation of the whole tangent space. Useful to solve optimization problems over those spaces.
dsqrtm : compute the Fréchet derivatives of matrix functions.
- Trust-region solver:
- As of Manopt 1.0.6, the inner solver tCG monitors the model cost; an (innocuous) logic bug was corrected there. Theory behind this feature is now better understood (a paper reference + BibTex was added).
- Warns if many TR+ / TR- steps are detected, to suggest changing parameter values.
- Uses safe version of tic/toc timers (originally because Octave now supports them).
- In case rho evaluates to NaN (which really should not happen), the code now ensures that the step is rejected and the radius decreased, thus preventing stagnation. In an adversely crafted example, this helped the solver escape the region where NaN's appear (again, this is not supposed to happen, but it's good to handle it nonetheless).
- Many more comments inside the code.
- New examples:
- robust_pca, illustrating how to smooth a nonsmooth cost function (here, on the Grassmann manifold).
- low_rank_dist_completion, illustrating usage of Manopt as a building block in a rank-incremental optimization algorithm for SDP.
- dominant_invariant_subspace_complex, adapting dominant_invariant_subspace to the complex case.
- radio_interferometric_calibration, illustrating the usage of the complex fixed-rank manifold.
- nonlinear_eigenspace, showing how to address certain nonlinear eigenvalue problems.
- essential_svd, demonstrating the new geometry essentialfactory.
- generalized_eigenvalue_computation, shows how to use grassmanngeneralizedfactory to solve generalized eigenvalue problems.
- shapefit_smoothed, does sensor network localization from pairwise direction measurements, following the ShapeFit paper.
- New cost description function: sqrtprecon, for the square root of the preconditioner (used in hessianspectrum).
- The privatetools directory is now named core, and is documented.
- Manopt 1.0.7, packaged August 12, 2014.
- Added the
ehess2rhess function to complexcirclefactory.
- Major revision of fixedrankembeddedfactory for support of optimization over fixed-rank matrices. It is now better documented, comes with an example called low_rank_matrix_completion, and now has support for
tangent2ambient, a proper vector transport, works with the hessianspectrum tool, ... This revision was executed with the precious and frequent help of Bart Vandereycken, who first described this geometry in a paper.
- All solvers now also return the
options structure, to make it easier to investigate what options a solver uses and what their default values are.
- It is now possible to specify a line-search hint function in the
problem structure; the result of that function will be used as a first guess in an Armijo backtracking line-search procedure, linesearch_hint. This is very useful if, for a given problem, you are able to make a good guess at how far along the search line one should look. It is much easier this way than with the previous way, which required implementing a whole new line-search algorithm.
- Generally improved textual outputs (warnings, iteration information, stopping reasons...).
- The documentation (tutorial, reference) was updated to reflect all of these changes.
- The sympositivedefinitefactory now has the correct dim() function and implements a new vector transport as explained in the example.
- Manopt 1.0.6, packaged June 25, 2014.
- For uses of the trustregions solver with a nonlinear approximation of the Hessian (such as, for example, the default one if you do not specify a Hessian at all), the truncated-CG algorithm now explicitly checks that the model cost decreases with (inner) iterations. If an increase is witnessed (which is bad), tCG now returns the best step so far, which is always at least the Cauchy step.
- The sympositivedefinitefactory geometry for positive definite matrices was revised. It had a number of mistakes in it due to an incorrect assumption. You can access the file before 1.0.6 is released on the forum.
- Small bug fix in packing_on_the_sphere example, along an improvement of how the smoothing term is computed numerically.
- Added a Riemannian Hessian conversion tool for the Stiefel manifold, ehess2rhess.
- Added a new (Euclidean) manifold, symmetricfactory, to deal with symmetric matrices.
- Multiple enhancements and bug fixes for the embedded geometry of fixed rank matrices fixedrankembeddedfactory: now works with checkgradient, changed hash and typical dist, and the vector transport is now correct (it was wrong before, leading to failure of CG and RTR-FD). Thanks to Bart Vandereycken for the correct code.
- Random vector generation in Stiefel and Grassmann now make more sense.
- PSO (Particle Swarm Optimization) solver debugged to work with product and power manifolds too.
- Bug fix in grassmannfactory's retraction for k > 1, and added final re-orthonormalization at the end of exponential map following forum discussions.
- The functions in elliptopefactory are now a tad faster, using bsxfun.
- Manopt 1.0.5, packaged January 2nd, 2014.
- Many files are now better commented and documented. In particular, the solvers now have quite complete documentation in code, available using Matlab's help command.
- The trust region solver was modified substantially. The algorithm is now slightly different from the previous versions, but is cleaner in its handling of errors, and behaves almost the same as before for normal operations. In particular, the fine-convergence heuristic has been changed to match a standard heuristic from the literature (see in code for references and the relevant option). The online documentation was extended as well. The original trust region radius (Delta0 and Delta_bar) are now interpreted correctly. Their values are different from earlier Manopt versions as a result. if you get a lot of TR+ or TR- for the first few iterations, you may want to tweak those options.
- New geometry: sympositivedefinitefactory, for symmetric, positive definite matrices. Related example script: positive_definite_karcher_mean.m.
- Line search algorithms have been heavily modified. The basic line search for example is now invariant under shifting and rescaling of the cost function, and the built-in line search algorithms now accept options too. Line searches now do not expect to be given a normalized search direction anymore, and they can decide whether to use the norm as supplemental information or to be unaffected by it. For example, the default line search for the conjugate gradient solver (the adaptive line search) is not invariant to the norm of the search direction.
- New example for sparse PCA via optimization on the Stiefel manifold.
- Potential bug (that never triggered) with purgeStoredb corrected.
- Manopt 1.0.4, packaged August 22nd, 2013.
- This release is a first step toward compatibility with Octave. We're not there yet, but in the examples folder, you will find maxcut_octave.m (removed in 1.0.8), which should run in Octave 3.6.4. In there, more info about compatibility issues and limitations are provided.
- Manopt is not organized in a Matlab package anymore (so folders are called folder and not +folder): no
import's anymore. Simply call
importmanopt to add all Manopt functions to the path, once.
- Sign error in right hand side of Lyapunov equation in
- Manopt 1.0.3, packaged July 26, 2013.
- The new /manopt/examples directory now contains documented examples.
- Added manifolds spectrahedron and elliptope, for symmetric positive semidefinite fixed-rank matrices with constraints on the diagonal or the trace. Notably useful for max-cut like SDP relaxations (see examples) and correlation matrix approximation / completion etc.
- The Riemannian gradient and Hessian may be given via their Euclidean counterparts, using
- Added Riemannian log map for the Grassmann manifold.
ehess2rhess available in more geometries.
- Added the tool
hessianspectrum to compute the eigenvalues of the Hessian (w/ or w/o preconditioner).
- Added notions of
tangent2ambient to manifolds.
- Added notions of
mat for manifolds, to represent tangent vectors as column vectors.
- Manopt 1.0.2, packaged June 11, 2013.
- Improved trustregions solver (e.g., avoids a redundant Hessian computation).
- Improved conjugategradient solver: now admits preconditioning.
- Reorganized fixedrank geometries (not backward compatible).
- Many small improvements and bug fixes.