Convex Relaxations for Recovering Simultaneously Structured Objects

on YouTube ↗40m

" summary

Claim: combining convex penalties (weighted sums or pointwise maxima of structure-promoting norms) fails to exploit multiple structures and requires as many measurements as the best single norm. Proof uses subdifferential geometry and random-matrix concentration (Gaussian and entry-sampling ensembles) to show sample complexity scales like n·kappa_min^2; for a sparse and low-rank rank-one lifted matrix this becomes Θ(min{k^2, n}), matching simulations and tight for Gaussians. The remedy is an atomic norm built from the true atoms, often computationally intractable.

AI-written summary · about

" chapters (12)

1. 0:00Start
2. 0:40Low-dimensional structure
3. 2:35Typical structures
4. 7:02Sparse and low-rank matrices: an application
5. 9:18Recovery of structured models
6. 12:08Example: Low-rank matrices and X.
7. 15:41Results summary
8. 16:26Sufficient condition for failure
9. 23:20Bound the lefthand side via random matrix theory
10. 28:45Sparse and low-rank case
11. 30:02Numerical experiments
12. 31:13A related problem: Denoising