Timeline for Proving convergence of modified ALS for non-negative matrix factorization
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 30, 2017 at 20:08 | comment | added | Suvrit | What that example is showing is that ALS is not even an alternating descent method, forget about alternating minimization. So without further work, it may not even converge. I remember observing non-convergent behavior, at least to the extent that ALS was behaving non-monotonically and ultimately reaching a worse "solution" --- will have to look into my old work to see if I can dig out a counterexample. | |
| Jul 30, 2017 at 18:30 | comment | added | nick.schachter | The example shown in section 2.1 doesn't seem to show oscillation, only that on a single iteration the objective function may be increased. It does not show that further iterations will not reach a local minimum. For what it's worth, I was aware that the ALS algorithm with truncation can have intermediate solutions that are worse than prior steps wrt the objective function, the overriding question seems to be showing whether or not this can be overcome. | |
| Jul 30, 2017 at 12:09 | comment | added | Suvrit | You should look at the explicit counterexamples in Sec 2.1 of my linked paper. I've now added a link to a version of the paper available from my website: suvrit.de/papers/kim_sra_nmf.pdf | |
| Jul 30, 2017 at 3:43 | comment | added | nick.schachter | It's somewhat unclear to me whether or not this oscillation is because the solution is not unique (as solutions to the NMF problem are subject to scaling for obvious reasons) or because the algorithm is actually getting stuck on values that are not valid solutions to the original problem. I cannot read parts of your paper because I do not have access, so perhaps my questions are addressed therein. | |
| Jul 29, 2017 at 16:09 | comment | added | Suvrit | But you do see that ALS can oscillate, right? | |
| Jul 29, 2017 at 16:04 | comment | added | nick.schachter | I appreciate the link to your past paper. In my experience, the difference in speed between ALS with truncation and A-NNLS has been substantial (an order of magnitude or greater on optimized C code) with little to no improvement in performance. Regardless, I am investigating the convergence of this algorithm specifically, so my question remains unresolved. | |
| Jul 28, 2017 at 23:22 | history | answered | Suvrit | CC BY-SA 3.0 |