Reconstructing Continuous Signals via Leverage Score Sampling
summary
Gives a tight, computable sample-complexity for recovering continuous signals under any Fourier prior and an efficient algorithm that actually constructs the interpolant. Uses ridge leverage scores to pick nonuniform time samples, builds a kernel matrix from the weighted inverse Fourier transform, and solves kernel ridge regression to produce ỹ with error ≲ ε·||x||_μ^2 + O(noise). Sample count equals the statistical dimension s_μ(ε) (matches FT for bandlimited and known polynomial/sparse bounds).
AI-written summary · about
chapters (27)
- 0:00Intro
- 1:04BASIC PROBLEM
- 2:04CONTINUOUS SIGNAL RECONSTRUCTION
- 2:56BANDLIMITED SIGNALS
- 3:45BANDLIMITED SIGNAL RECONSTRUCTION
- 4:38PROBLEMS WITH SING INTERPOLATION
- 6:32PROLATE SPHEROIDAL WAVE FUNCTIONS
- 9:31NON-UNIFORM SAMPLING
- 10:07WHAT ABOUT OTHER STRUCTURE?
- 10:19FOURIER TRANSFORM STRUCTURE
- 11:35GENERAL FOURIER STRUCTURE
- 15:31FORMAL PROBLEM STATEMENT
- 17:17INTUITION FOR INDICATOR PRIORS
- 18:04NATURAL APPROACH
- 20:28HANDLING FOURIER DOMAIN
- 21:02EQUIVALENCE TO KERNEL REGRESSION
- 21:15TIME DOMAIN DISCRETIZATION
- 22:08STATISTICAL DIMENSION
- 23:21LEVERAGE SCORE SAMPLING
- 23:49LEVERAGE SCORES
- 24:33POLYNOMIAL LEVERAGE
- 26:22FOURIER SPARSE LEVERAGE
- 27:07GENERAL CONSTRAINTS
- 27:19GENERAL LEVERAGE
- 27:34SPARSE APPROXIMATION OF WEIGHTED FOURIER TRANSFORM
- 28:18FINAL BOUND
- 28:40FINAL ALGORITHM
related talks
01h 04mSketching for Linear Algebra III: Randomized Hadamard, Kernel Methods
01h 02mSampling for Linear Algebra, Statistics, and Optimization II
33mRandomized Least Squares Optimization and its Incredible Utility for Large-Scale Tensor Decomp...
01h 26mStreaming, Sketching and Sufficient Statistics II
40mGoing Off the Grid
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
44mActive Regression via Linear-Sample Sparsification
37mLow-rank Matrix Completion: Adaptive Sampling Can Help When, How?