Differences
This shows you the differences between two versions of the page.
|
courses:sp21:e9-203:lectures [2021/06/11 03:09] cmurthy |
courses:sp21:e9-203:lectures [2021/06/11 11:34] (current) cmurthy |
||
|---|---|---|---|
| Line 3: | Line 3: | ||
| * Lecture 1: Introduction to underdetermined linear systems, penalty functions, l1 minimization, and linear programming. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_02_26.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 02 26.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 02 26.pdf|Notes-PDF]]. | * Lecture 1: Introduction to underdetermined linear systems, penalty functions, l1 minimization, and linear programming. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_02_26.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 02 26.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 02 26.pdf|Notes-PDF]]. | ||
| - | * Lecture 2: Best s-term approximation, and why lp-ball with p < 1 promotes sparsity. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_03_01a.mp4|Video1]], [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_03_01b.mp4|Video2]],[[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 03 01.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 03 01.pdf|Notes-PDF]]. | + | * Lecture 2: Best s-term approximation, and why lp-ball with p < 1 promotes sparsity. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_03_01a.mp4|Video1]], [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_03_01b.mp4|Video2]],[[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 03 01.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 03 01.pdf|Notes-PDF]]. |
| - | + | * Lecture 3: Tighter bounds on compressible signals, minimal number of measurements for unique sparse vector recovery. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_03_03.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 03 03.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 03 03.pdf|Notes-PDF]]. | |
| + | * Lecture 4: Minimal number of measurements for the recovery of all s-sparse vectors. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_03_05.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 03 05.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 03 05.pdf|Notes-PDF]]. | ||
| + | * Lecture 5: Recovery of individual sparse vectors. NP-hardness of l0 minimization. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_03_08.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 03 08.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 03 08.pdf|Notes-PDF]]. | ||
| + | * Lecture 6: L1 minimization leads to sparse solutions. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_03_10.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 03 10.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 03 10.pdf|Notes-PDF]]. | ||
| + | * Lecture 7: The orthogonal matching pursuit algorithm. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_03_12.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 03 12.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 03 12.pdf|Notes-PDF]]. | ||
| + | * Lecture 8: Thresholding based algorithms. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_03_15.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 03 15.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 03 15.pdf|Notes-PDF]]. | ||
| + | * Lecture 9: Regularization based methods. Extreme points, basic feasible solutions, and concave optimization. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_03_17.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 03 17.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 03 17.pdf|Notes-PDF]]. | ||
| + | * Lecture 10: Majorization-minimization based methods. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_03_19.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 03 19.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 03 19.pdf|Notes-PDF]]. | ||
| + | * Lecture 11: Reweighting based methods. Analysis of local minima. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_03_22.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 03 22.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 03 22.pdf|Notes-PDF]]. | ||
| + | * Lecture 12: Convergence of reweighting based methods. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_03_24.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 03 24.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 03 24.pdf|Notes-PDF]]. | ||
| + | * Lecture 13: Sparse Bayesian learning. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_03_26.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 03 26.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 03 26.pdf|Notes-PDF]]. | ||
| + | * Lecture 14: Sparse Bayesian learning - continued. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_03_29.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 03 29.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 03 29.pdf|Notes-PDF]]. | ||
| + | * Lecture 15: Discussion on the SBL prior, reweighted algorithms for SBL. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_03_31.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 03 31.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 03 31.pdf|Notes-PDF]]. | ||
| + | * Lecture 16: Reweighted l2 algorithms for SBL (continued), non-negative sparse recovery. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_04_05.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 04 05.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 04 05.pdf|Notes-PDF]]. | ||
| + | * Lecture 17: Basis pursuit (BP). [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_04_07.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 04 07.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 04 07.pdf|Notes-PDF]]. | ||
| + | * Lecture 18: Stable null space property, robust null space property. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_04_09.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 04 09.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 04 09.pdf|Notes-PDF]]. | ||
| + | * Lecture 19: Recovery of sparse vectors via robust null space property. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_04_12.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 04 12.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 04 12.pdf|Notes-PDF]]. | ||
| + | * Lecture 20: Recovery of individual sparse vectors. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_04_14.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 04 14.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 04 14.pdf|Notes-PDF]]. | ||
| + | * Lecture 21: A stable and robust recovery result. Recovery via tangent cones. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_04_16.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 04 16.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 04 16.pdf|Notes-PDF]]. | ||
| + | * Lecture 22: Low rank matrix recovery. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_04_19.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 04 19.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 04 19.pdf|Notes-PDF]]. | ||
| + | * Lecture 23: Coherence. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_04_21.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 04 21.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 04 21.pdf|Notes-PDF]]. | ||
| + | * Lecture 24: Properties of spark. Guarantees based on coherence. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_04_23.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 04 23.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 04 23.pdf|Notes-PDF]]. | ||
| + | * Lecture 25: Analysis of BP and thresholding-based algorithms via coherence. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_04_26.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 04 26.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 04 26.pdf|Notes-PDF]]. | ||
| + | * Lecture 26: The restricted isometry property. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_04_28.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 04 28.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 04 28.pdf|Notes-PDF]]. | ||
| + | * Lecture 27: Properties of and bounds on the restricted isometry constant (RIC). [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_04_30.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 04 30.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 04 30.pdf|Notes-PDF]]. | ||
| + | * Lecture 28: Analysis of BP via RIC. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_05_03.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 05 03.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 05 03.pdf|Notes-PDF]]. | ||
| + | * Lecture 29: Analysis of thresholding algorithms via RIC. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_05_05.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 05 05.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 05 05.pdf|Notes-PDF]]. | ||
| + | * Lecture 30: Proof of the result on the analysis of thresholding algorithms via RIC. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_05_07.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 05 07.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 05 07.pdf|Notes-PDF]]. | ||
| + | * Lecture 31: Analysis of greedy algorithms (OMP) via RIC. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_05_10.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 05 10.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 05 10.pdf|Notes-PDF]]. | ||
| + | * Lecture 32: Gaussian matrices satisfy RIP. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_05_12.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 05 12.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 05 12.pdf|Notes-PDF]]. | ||
| + | * Lecture 33: Gaussian matrices satisfy RIP (continued). [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_05_14.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 05 14.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 05 14.pdf|Notes-PDF]]. | ||
| + | * Lecture 34: RIP results for subgaussian matrices, Johnson Lindenstrauss lemma. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_05_17.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 05 17.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 05 17.pdf|Notes-PDF]]. | ||
| + | * Lecture 35: Algorithms for l1 regularization. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_05_19.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 05 19.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 05 19.pdf|Notes-PDF]]. | ||
| + | * Lecture 36: Proximal and gradient projection methods. Gelfand m-widths defined. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_05_21.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 05 21.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 05 21.pdf|Notes-PDF]]. | ||
| + | * Lecture 37: Bounds on Gelfand m-widths. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_05_24.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 05 24.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 05 24.pdf|Notes-PDF]]. | ||
| + | * Lecture 38: Proof of the result on the bounds on Gelfand m-widths. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_05_26.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 05 26_1.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 05 26_1.pdf|Notes-PDF]]. | ||
| + | * Lecture 39: Further results and explanation of bounds on Gelfand m-widths. [[http://ece.iisc.ac.in/~cmurthy/E9203/2021_05_28.mp4|Video]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 05 28.svg|Notes-SVG]], [[http://ece.iisc.ac.in/~cmurthy/E9203/E9 203 2021 05 28.pdf|Notes-PDF]]. | ||
