Online Algorithms for Low Rank Approximation
summary
Proposes an online algorithm that produces a low‑dimensional embedding achieving a one‑plus‑epsilon approximation for PCA under two assumptions: a rough estimate of OPT and a polynomial bound on sigma_max/OPT. Uses a phasewise adaptive‑sampling scheme that stores one random‑signed linear sketch per phase, yields about K·poly(log N/ε) output dimensions (or K·O(log N) phases) and combines a sketching black box to reach multiplicative error; works subject to the stated constraints and leaves single‑pass optimality and removal of condition‑number dependence open.
AI-written summary · about
chapters (12)
- 0:00Introduction to the problems
- 1:06Defining the core objectives
- 4:15Online algorithm setup
- 7:35Formalizing online PCA
- 10:24State of the art and approach
- 14:07Meyerson's algorithm analysis
- 17:54Developing the new algorithm
- 23:03Geometric lemmas for bounds
- 28:37Phase-based algorithm logic
- 34:43Multiplicative approximation
- 36:57Closing and open questions
- 43:10Q&A and concluding remarks