Implementation of a more generic fixed-rank manifold? #23

Open
a378ec99 opened this Issue Jul 8, 2016 · 11 comments

Comments

Projects
None yet
3 participants
@a378ec99

a378ec99 commented Jul 8, 2016

When working on matrix recovery problems, often a more generic low-rank matrix is thought after than the currently implemented symmetric positive semi-definite matrix. Could someone implement one of the respective manifolds provided in manopt? Is something already in the works?

@j-towns j-towns added the enhancement label Jul 11, 2016

@j-towns

This comment has been minimized.

Show comment
Hide comment
@j-towns

j-towns Jul 11, 2016

Member

Hi there, thanks for the request. I agree we should have some options for generic low-rank matrices. We'll look into this and let you know when we have something implemented.

Member

j-towns commented Jul 11, 2016

Hi there, thanks for the request. I agree we should have some options for generic low-rank matrices. We'll look into this and let you know when we have something implemented.

@a378ec99

This comment has been minimized.

Show comment
Hide comment
@a378ec99

a378ec99 Jul 28, 2016

Great. Are you able to give an estimate on the time it may take to close the issue, e.g. days, weeks, or months?

Great. Are you able to give an estimate on the time it may take to close the issue, e.g. days, weeks, or months?

@j-towns

This comment has been minimized.

Show comment
Hide comment
@j-towns

j-towns Jul 28, 2016

Member

We're working on it now, nearly done. Should hopefully be done by the end of today. If not then tomorrow 🙂

Member

j-towns commented Jul 28, 2016

We're working on it now, nearly done. Should hopefully be done by the end of today. If not then tomorrow 🙂

@j-towns

This comment has been minimized.

Show comment
Hide comment
@j-towns

j-towns Jul 28, 2016

Member

the manifold we are currently implementing is from Manopt's fixedrankembeddedfactory.m

Member

j-towns commented Jul 28, 2016

the manifold we are currently implementing is from Manopt's fixedrankembeddedfactory.m

@sweichwald

This comment has been minimized.

Show comment
Hide comment
@sweichwald

sweichwald Jul 29, 2016

Member

Hi.
We have implemented the above manifold, currently only supporting the autograd autodiff backend. But theano and tensorflow should be fixed soon (~1-2 weeks).
You can install this updated version like this:
pip install git+https://github.com/pymanopt/pymanopt.git --upgrade
Please let us know if there are any problems.
Cheers.

Member

sweichwald commented Jul 29, 2016

Hi.
We have implemented the above manifold, currently only supporting the autograd autodiff backend. But theano and tensorflow should be fixed soon (~1-2 weeks).
You can install this updated version like this:
pip install git+https://github.com/pymanopt/pymanopt.git --upgrade
Please let us know if there are any problems.
Cheers.

@sweichwald sweichwald closed this Jul 29, 2016

@a378ec99

This comment has been minimized.

Show comment
Hide comment
@a378ec99

a378ec99 Jul 29, 2016

Great! The Autograd backend is what I am using at the moment. I'll let you know if there are any issues with the current implementation. Best.

Great! The Autograd backend is what I am using at the moment. I'll let you know if there are any issues with the current implementation. Best.

@j-towns

This comment has been minimized.

Show comment
Hide comment
@j-towns

j-towns Jul 29, 2016

Member

We've also written a simple example for using this manifold: https://github.com/pymanopt/pymanopt/blob/master/examples/low_rank_matrix_approximation.py

The solvers return an array of type _Point for this manifold (something we will iron out when we have time). For now this can easily be cast to a numpy.ndarray by doing numpy.array(x).

Member

j-towns commented Jul 29, 2016

We've also written a simple example for using this manifold: https://github.com/pymanopt/pymanopt/blob/master/examples/low_rank_matrix_approximation.py

The solvers return an array of type _Point for this manifold (something we will iron out when we have time). For now this can easily be cast to a numpy.ndarray by doing numpy.array(x).

@j-towns

This comment has been minimized.

Show comment
Hide comment
@j-towns

j-towns Jul 29, 2016

Member

Reopening until we have sorted out Theano and Tensorflow backends.

Member

j-towns commented Jul 29, 2016

Reopening until we have sorted out Theano and Tensorflow backends.

@j-towns j-towns reopened this Jul 29, 2016

@j-towns

This comment has been minimized.

Show comment
Hide comment
@j-towns

j-towns Aug 23, 2016

Member

838cf87

In the interests of simplicity and efficiency, we've decided that points on this manifold should be parameterised via their low rank svd. That is, they are parameterised similarly to the output of numpy.linalg.svd, as a tuple (u, s, vt), where u is a m x k array, s is a length k vector and vt is a k x n array.

The full low rank matrix can be reconstructed with

a = np.dot(u, np.dot(np.diag(s), vt))

and cost functions defined in terms of this reconstructed matrix.

See https://github.com/pymanopt/pymanopt/blob/master/examples/low_rank_matrix_approximation.py for a full example. I will also be writing a blog post about this, I will add a link when it's done.

Note that you can now define cost functions using Theano or TensorFlow, however the second order trust regions solver is not yet working on this manifold. Hope that's ok, let us know if you have any issues.

Member

j-towns commented Aug 23, 2016

838cf87

In the interests of simplicity and efficiency, we've decided that points on this manifold should be parameterised via their low rank svd. That is, they are parameterised similarly to the output of numpy.linalg.svd, as a tuple (u, s, vt), where u is a m x k array, s is a length k vector and vt is a k x n array.

The full low rank matrix can be reconstructed with

a = np.dot(u, np.dot(np.diag(s), vt))

and cost functions defined in terms of this reconstructed matrix.

See https://github.com/pymanopt/pymanopt/blob/master/examples/low_rank_matrix_approximation.py for a full example. I will also be writing a blog post about this, I will add a link when it's done.

Note that you can now define cost functions using Theano or TensorFlow, however the second order trust regions solver is not yet working on this manifold. Hope that's ok, let us know if you have any issues.

@a378ec99

This comment has been minimized.

Show comment
Hide comment
@a378ec99

a378ec99 Feb 21, 2017

Note that only SteepestDescent and ConjugateGradient solvers are working at the moment, while TrustRegions, NelderMead, ParticleSwarm fail. In some cases this seems to be due to the svd/tuple data structure for the low-rank matrix. It would be nice to try out more solvers when benchmarking...

Note that only SteepestDescent and ConjugateGradient solvers are working at the moment, while TrustRegions, NelderMead, ParticleSwarm fail. In some cases this seems to be due to the svd/tuple data structure for the low-rank matrix. It would be nice to try out more solvers when benchmarking...

@j-towns

This comment has been minimized.

Show comment
Hide comment
@j-towns

j-towns Feb 21, 2017

Member

There are two unimplemented methods which are necessary for those solvers. ehess2rhess is necessary for TrustRegions and dist is necessary for NelderMead and ParticleSwarm.

To implement ehess2rhess someone needs to do some slighty tricky derivation to work out the correct form for our parameterization (which is a bit different to Manopt). If I have time at some point I can do this. In case someone else is thinking of having a go, this may come in handy: https://j-towns.github.io/papers/svd-derivative.pdf. The reason we've left this issue open is to remind ourselves to do this at some point.

I believe the correct form of this manifold's dist method, which calculates the geodesic distance between two points on the manifold, is not known, and it's an open problem to work this out. I don't know whether it would be possible to come up with a good approximation. One very naive thing that comes to mind is just the Frobenius distance between the two matrices, and this might do for the purposes of those two solvers.

Member

j-towns commented Feb 21, 2017

There are two unimplemented methods which are necessary for those solvers. ehess2rhess is necessary for TrustRegions and dist is necessary for NelderMead and ParticleSwarm.

To implement ehess2rhess someone needs to do some slighty tricky derivation to work out the correct form for our parameterization (which is a bit different to Manopt). If I have time at some point I can do this. In case someone else is thinking of having a go, this may come in handy: https://j-towns.github.io/papers/svd-derivative.pdf. The reason we've left this issue open is to remind ourselves to do this at some point.

I believe the correct form of this manifold's dist method, which calculates the geodesic distance between two points on the manifold, is not known, and it's an open problem to work this out. I don't know whether it would be possible to come up with a good approximation. One very naive thing that comes to mind is just the Frobenius distance between the two matrices, and this might do for the purposes of those two solvers.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment