Learning a Hidden Basis through Imperfect Measurements: Why and How
summary
Algorithm recovers an unknown orthonormal partial basis from evaluations and gradients of F(u)=sum_i g_i(u·e_i) by iterating gradient iteration (replace u by normalized ∇F(u)); under the key assumption that each g_i(√x) is strictly convex the only stable fixed points are ±e_i and with intelligent restarts one recovers all basis vectors. For g_i(t)=t^r convergence is super-linear (order r−1), perturbation analysis controls gradient/Hessian noise (cubic case yields O(√m·ε) error) and gives Davis–Kahan–style bounds and iteration counts.
AI-written summary · about
chapters (13)
- 0:00Intro
- 1:28Hidden Basis Recovery
- 3:38Example: PCA
- 4:36Example: tensor decomposition
- 5:23Example: Independent component Analysis
- 6:20Example: Gaussian Mixture Models
- 6:43Application: Spectral clustering
- 7:15Recovering the basis: "gradient iteration" algorithm
- 11:25Conditions on gi
- 13:25Hidden convexity
- 17:02Finding the hidden basis
- 18:57Perturbation Analysis: model
- 23:53Summary
related talks
29mImplicit Regularization in Nonconvex Statistical Estimation
01h 30mAnalytic Methods for Supervised Learning IV
01h 06mAnalytic Methods for Supervised Learning III
27mOptimal Spectral Recovery Of A Planted Vector In A Subspace
01h 05mFirst-Order Optimization and Online Learning Techniques in the Design of Fast Spectral Algorithms
27mAlmost-Orthogonal Bases for Inner Product Polynomials
51mFirst-Order Methods and Hyperbolic Programming
36mPrivately Learning High-Dimensional Distributions