Two Concise Representations for High-Dimensional Visual Data
Talkat Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013) · 2013-09-16..09-19·
summary
Derives two concrete representations and proofs: images under varying illumination admit a low-rank + sparse decomposition enabling convex recovery (exact under incoherence) and a covering bound that requires about 1/γ^2 samples for convex objects but about 1/γ^4 for nonconvex ones; for dictionary learning a global algorithm recovers a complete dictionary from roughly n log n samples while the provable overcomplete regime needs about n^2 log n samples and only tolerates ~√n nonzeros per column, with simulations showing a sharp success/failure transition.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 1:37The Problem
- 5:09Popular Engineering Approaches
- 9:44Standard Model
- 14:29Literature
- 18:26Analysis
- 34:26Global Results
- 37:34Algorithms
- 38:52Hyperplanes
- 41:23Algorithm
- 43:40Proof
- 45:49Simulation
related talks
01h 03mRecent Progress in High-Dimensional Learning
01h 14mRecent Progress in High-Dimensional Learning
01h 34mAlgorithmic High-Dimensional Geometry I
25mSimple, Efficient and Neural Algorithms for Sparse Coding
49mRobust PCA via Non-convex Methods: Provable Bounds
01h 07mRecent Progress in High-Dimensional Learning
01h 10mSketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch II
45mHigh Dimensional Robust Sparse Regression