Skip to first unread message
Yuanming Shi
Jan 5, 2015, 10:28:59 AM1/5/15
to manopt...@googlegroups.com
Hi,
I am using Manopt and find it fantastic! Actually, I am trying to solve the rank minimization problem instead of fixed-rank problem. A trivial way is to use a rank increase approach to find an optimum for the rank minimisation problem if we can solve the fixed-rank problem globally. But, Manopt may only return a local optimum. Do you have some user-friendly suggestions on this case?
Best.
I am using Manopt and find it fantastic! Actually, I am trying to solve the rank minimization problem instead of fixed-rank problem. A trivial way is to use a rank increase approach to find an optimum for the rank minimisation problem if we can solve the fixed-rank problem globally. But, Manopt may only return a local optimum. Do you have some user-friendly suggestions on this case?
Best.
Nicolas Boumal
Jan 5, 2015, 11:15:44 AM1/5/15
to manopt...@googlegroups.com
Hello Yuanming,
Thank you for the feedback and the question.
My short answer is that minimizing the rank is usually hard (like, NP-hard), and hence there will be no perfect algorithm for your purpose. So we turn to heuristics (often). Using Manopt in the way you described (increasing the rank bit by bit, knowing that at each step we might get merely a local optimizer) is one reasonable way to proceed. Since there will be no or few theoretical guarantees, we're left to numerically experiment to see if that works well or not on specific applications.
There is a nice paper by Bart Vandereycken at NOLTA 2014 here, where such a strategy is used with good performance on low-rank matrix completion:
http://web.math.princeton.edu/~bartv/nolta14.html
Cheers,
Nicolas
Thank you for the feedback and the question.
My short answer is that minimizing the rank is usually hard (like, NP-hard), and hence there will be no perfect algorithm for your purpose. So we turn to heuristics (often). Using Manopt in the way you described (increasing the rank bit by bit, knowing that at each step we might get merely a local optimizer) is one reasonable way to proceed. Since there will be no or few theoretical guarantees, we're left to numerically experiment to see if that works well or not on specific applications.
There is a nice paper by Bart Vandereycken at NOLTA 2014 here, where such a strategy is used with good performance on low-rank matrix completion:
http://web.math.princeton.edu/~bartv/nolta14.html
Cheers,
Nicolas
Reply all
Reply to author
Forward
0 new messages