Recovery Guarantee of Non-Negative Matrix Factorization via Alternating Updates
summary
Alternate-update NMF uses pseudo-inverse + ReLU decoding (decode x = ReLU(A†y − α)) then update A by the empirical expectation of (y y') (x x')^T using fresh sample batches; assumes A columns are linearly independent and X coordinates are independent with sparse {0,1} activations. From a constant-accuracy warm start the method reduces column error to ε in O(log(1/ε) iterations) with polynomial samples, requires tuned α and step sizes, and tolerates adversarial entrywise noise*.
AI-written summary · about
chapters (19)
- 0:00Introduction
- 0:17Machine Learning Applications
- 1:01Practical Applications
- 1:29Gradient Descent
- 2:22Alternating Updates
- 4:02Discussion
- 6:48NonNegative Matrix Factorization
- 7:21Topic Modeling
- 10:04Computer Vision
- 14:40NMF
- 19:59Algorithm
- 22:39Update
- 25:07sanity check
- 25:53update check
- 26:29linear independence
- 31:55decoding
- 35:56update direction
- 38:52highlevel intuition
- 41:53setting up
related talks
23mLow-Rank Matrix Recovery Through Rank-One Projections
51mNearly Linear Time Algorithms for Solving Inverse Symmetric M-Matrices
29mRecent Advances in Positive Semidefinite Matrix Approximation
32mRandomized Numerical Linear Algebra: Overview
37mLow-rank Matrix Completion: Adaptive Sampling Can Help When, How?
34mMatrix Martingales in Randomized Numerical Linear Algebra
01h 27mPast, Present and Future of Randomized Numerical Linear Algebra I
46mSolvable Model of Unsupervised Feature Learning