Gabriel Peyré, profile picture
Uploaded byGabriel Peyré
PDF, PPTX1,342 views

Low Complexity Regularization of Inverse Problems

This document discusses regularization techniques for inverse problems. It begins with an overview of compressed sensing and inverse problems, as well as convex regularization using gauges. It then discusses performance guarantees for regularization methods using dual certificates and L2 stability. Specific examples of regularization gauges are given for various models including sparsity, structured sparsity, low-rank, and anti-sparsity. Conditions for exact recovery using random measurements are provided for sparse vectors and low-rank matrices. The discussion concludes with the concept of a minimal-norm certificate for the dual problem.

Download as PDF, PPTX
Low Complexity Regularization of Inverse Problems Gabriel Peyré Joint works with: Samuel Vaiter Jalal Fadili Charles Dossal Mohammad Golbabaee VISI www.numerical-tours.com N
Overview • Compressed Sensing and Inverse Problems • Convex Regularization with Gauges • Performance Guarantees
Single Pixel Camera (Rice) x0 ˜
Single Pixel Camera (Rice) x0 ˜ y[i] = hx0 , 'i i P measures N micro-mirrors
Single Pixel Camera (Rice) x0 ˜ y[i] = hx0 , 'i i P measures P/N = 1 N micro-mirrors P/N = 0.16 P/N = 0.02
CS Hardware Model ˜ CS is about designing hardware: input signals f L2 (R2 ). Physical hardware resolution limit: target resolution f 2 x0 2 L ˜ array resolution CS hardware x0 2 R N micro mirrors RN . y 2 RP
CS Hardware Model ˜ CS is about designing hardware: input signals f L2 (R2 ). Physical hardware resolution limit: target resolution f x0 2 L ˜ array resolution x0 2 R N micro mirrors y 2 RP CS hardware , , ... 2 RN . , Operator x0
Inverse Problems Recovering x0 RN from noisy observations y = x 0 + w 2 RP
Inverse Problems Recovering x0 RN from noisy observations y = x 0 + w 2 RP Examples: Inpainting, super-resolution, compressed-sensing x0 x0
Inverse Problem Regularization Observations: y = x0 + w 2 RP . Estimator: x(y) depends only on observations y parameter
Inverse Problem Regularization Observations: y = x0 + w 2 RP . Estimator: x(y) depends only on observations y parameter Example: variational methods 1 x(y) 2 argmin ||y x||2 + J(x) x2RN 2 Data fidelity Regularity
Inverse Problem Regularization Observations: y = x0 + w 2 RP . Estimator: x(y) depends only on observations y parameter Example: variational methods 1 x(y) 2 argmin ||y x||2 + J(x) x2RN 2 Data fidelity Regularity Performance analysis: ! Criteria on (x0 , ||w||, ) to ensure L2 stability ||x(y) x0 || = O(||w||) Model stability (e.g. spikes location)
Overview • Compressed Sensing and Inverse Problems • Convex Regularization with Gauges • Performance Guarantees
Union of Linear Models for Data Processing Union of models: T 2 T linear spaces. Synthesis sparsity: T Coe cients x Image x
Union of Linear Models for Data Processing Union of models: T 2 T linear spaces. Synthesis sparsity: Structured sparsity: T Coe cients x Image x
Union of Linear Models for Data Processing Union of models: T 2 T linear spaces. Synthesis sparsity: Structured sparsity: T Coe cients x Image x D Analysis sparsity: Image x Gradient D⇤ x
Union of Linear Models for Data Processing Union of models: T 2 T linear spaces. Synthesis sparsity: Structured sparsity: T Coe cients x Analysis sparsity: Image x D Low-rank: Image x Gradient D⇤ x S1,· Multi-spectral imaging: Pr xi,· = j=1 Ai,j Sj,· S2,· x S3,·
Gauges for Union of Linear Models Gauge: J :R N !R + Convex 8 ↵ 2 R+ , J(↵x) = ↵J(x)
Gauges for Union of Linear Models Gauge: J :R N !R + Convex 8 ↵ 2 R+ , J(↵x) = ↵J(x) Piecewise regular ball , Union of linear models (T )T 2T x J(x) = ||x||1 T T = sparse vectors
Gauges for Union of Linear Models Gauge: J :R N !R + Convex 8 ↵ 2 R+ , J(↵x) = ↵J(x) Piecewise regular ball , Union of linear models (T )T 2T T0 x0 x J(x) = ||x||1 T T = sparse vectors
Gauges for Union of Linear Models Gauge: J :R N !R Convex 8 ↵ 2 R+ , J(↵x) = ↵J(x) + Piecewise regular ball , Union of linear models (T )T 2T T T0 x0 x J(x) = ||x||1 T T = sparse vectors x T0 x |x1 |+||x2,3 || T = block sparse vectors 0
Gauges for Union of Linear Models Gauge: J :R N !R Convex 8 ↵ 2 R+ , J(↵x) = ↵J(x) + Piecewise regular ball , Union of linear models (T )T 2T T T0 x0 x J(x) = ||x||1 T T = sparse vectors x T x |x1 |+||x2,3 || T = block sparse vectors 0 x 0 J(x) = ||x||⇤ T = low-rank matrices
Gauges for Union of Linear Models Gauge: J :R N !R Convex 8 ↵ 2 R+ , J(↵x) = ↵J(x) + Piecewise regular ball , Union of linear models (T )T 2T T T0 x0 x J(x) = ||x||1 T T = sparse vectors T0 x T x |x1 |+||x2,3 || T = block sparse vectors 0 x x x0 0 J(x) = ||x||⇤ T = low-rank matrices J(x) = ||x||1 T = antisparse vectors
Subdifferentials and Models @J(x) = {⌘ 8 y, J(y) > J(x)+h⌘, y xi} |x|
Subdifferentials and Models @J(x) = {⌘ 8 y, J(y) > J(x)+h⌘, y |x| xi} Example: J(x) = ||x||1 ⇢ supp(⌘) = I, @||x||1 = ⌘ 8 j 2 I, |⌘j | 6 1 / I = supp(x) = {i xi 6= 0} @J(x) 0 x
Subdifferentials and Models @J(x) = {⌘ 8 y, J(y) > J(x)+h⌘, y |x| xi} Example: J(x) = ||x||1 ⇢ supp(⌘) = I, @||x||1 = ⌘ 8 j 2 I, |⌘j | 6 1 / I = supp(x) = {i xi 6= 0} Tx = {⌘ supp(⌘) = I} Definition: Tx = VectHull(@J(x))? @J(x) 0 x Tx
Subdifferentials and Models @J(x) = {⌘ 8 y, J(y) > J(x)+h⌘, y |x| xi} Example: J(x) = ||x||1 ⇢ supp(⌘) = I, @||x||1 = ⌘ 8 j 2 I, |⌘j | 6 1 / @J(x) 0 I = supp(x) = {i xi 6= 0} Tx Tx = {⌘ supp(⌘) = I} ex = sign(x) Definition: Tx = VectHull(@J(x))? ⌘ 2 @J(x) ex x =) ProjTx (⌘) = ex
Examples `1 sparsity: J(x) = ||x||1 ex = sign(x) x @J(x) x 0 Tx = {z supp(z) ⇢ supp(x)}
Examples `1 sparsity: J(x) = ||x||1 ex = sign(x) Tx = {z supp(z) ⇢ supp(x)} P Structured sparsity: J(x) = b ||xb || N (a) = a/||a|| ex = (N (xb ))b2B Tx = {z supp(z) ⇢ supp(x)} x @J(x) x 0 x @J(x) x 0
Examples `1 sparsity: J(x) = ||x||1 ex = sign(x) Tx = {z supp(z) ⇢ supp(x)} P Structured sparsity: J(x) = b ||xb || N (a) = a/||a|| ex = (N (xb ))b2B Tx = {z supp(z) ⇢ supp(x)} Nuclear norm: J(x) = ||x||⇤ ex = U V x @J(x) x 0 ⇤ x x = U ⇤V ⇤ SVD: ⇤ Tx = {z U? zV? = 0} @J(x) x 0 x @J(x)
Examples `1 sparsity: J(x) = ||x||1 ex = sign(x) Tx = {z supp(z) ⇢ supp(x)} P Structured sparsity: J(x) = b ||xb || N (a) = a/||a|| ex = (N (xb ))b2B Tx = {z supp(z) ⇢ supp(x)} Nuclear norm: J(x) = ||x||⇤ ex = U V ⇤ x = U ⇤V ⇤ SVD: ⇤ Tx = {z U? zV? = 0} I = {i |xi | = ||x||1 } Anti-sparsity: J(x) = ||x||1 Tx = {y yI / sign(xI )} ex = |I| 1 sign(x) x @J(x) x 0 x @J(x) @J(x) x 0 x @J(x) x x 0
Overview • Compressed Sensing and Inverse Problems • Convex Regularization with Gauges • Performance Guarantees
Dual Certificate and L2 Stability Noiseless recovery: min J(x) x= x0 (P0 ) x? x= x0
Dual Certificate and L2 Stability Noiseless recovery: min J(x) x= x0 (P0 ) Proposition: x0 solution of (P0 ) () 9 ⌘ 2 D(x0 ) Dual certificates: D(x0 ) = Im( ⇤ ⌘ x? ) @J(x0 ) @J(x0 ) x= x0
Dual Certificate and L2 Stability Noiseless recovery: min J(x) x= x0 (P0 ) Proposition: x0 solution of (P0 ) () 9 ⌘ 2 D(x0 ) Dual certificates: D(x0 ) = Im( ¯ Tight dual certificates: D(x0 ) = Im( ⇤ ⌘ @J(x0 ) x? ) @J(x0 ) ⇤ ) ri(@J(x0 )) x= x0
Dual Certificate and L2 Stability Noiseless recovery: min J(x) x= x0 (P0 ) Proposition: x0 solution of (P0 ) () 9 ⌘ 2 D(x0 ) Dual certificates: D(x0 ) = Im( ¯ Tight dual certificates: D(x0 ) = Im( Theorem: ¯ If 9 ⌘ 2 D(x0 ), for ⌘ @J(x0 ) x? x= x0 ⇤ ) @J(x0 ) ⇤ ) ri(@J(x0 )) [Fadili et al. 2013] ⇠ ||w|| one has ||x? x0 || = O(||w||)
Dual Certificate and L2 Stability Noiseless recovery: min J(x) x= x0 (P0 ) Proposition: x0 solution of (P0 ) () 9 ⌘ 2 D(x0 ) Dual certificates: D(x0 ) = Im( ¯ Tight dual certificates: D(x0 ) = Im( Theorem: ¯ If 9 ⌘ 2 D(x0 ), for ⌘ @J(x0 ) x? x= x0 ⇤ ) @J(x0 ) ⇤ ) ri(@J(x0 )) [Fadili et al. 2013] ⇠ ||w|| one has ||x? x0 || = O(||w||) [Grassmair, Haltmeier, Scherzer 2010]: J = || · ||1 . [Grassmair 2012]: J(x? x0 ) = O(||w||).
Compressed Sensing Setting Random matrix: 2 RP ⇥N , i,j ⇠ N (0, 1), i.i.d.
Compressed Sensing Setting Random matrix: 2 RP ⇥N , Sparse vectors: J = || · ||1 . Theorem: Let s = ||x0 ||0 . If i,j ⇠ N (0, 1), i.i.d. [Rudelson, Vershynin 2006] [Chandrasekaran et al. 2011] P > 2s log (N/s) ¯ Then 9⌘ 2 D(x0 ) with high probability on .
Compressed Sensing Setting Random matrix: 2 RP ⇥N , Sparse vectors: J = || · ||1 . Theorem: Let s = ||x0 ||0 . If i,j ⇠ N (0, 1), i.i.d. [Rudelson, Vershynin 2006] [Chandrasekaran et al. 2011] P > 2s log (N/s) ¯ Then 9⌘ 2 D(x0 ) with high probability on Low-rank matrices: J = || · ||⇤ . Theorem: Let r = rank(x0 ). If . [Chandrasekaran et al. 2011] x0 2 RN1 ⇥N2 P > 3r(N1 + N2 r) ¯ Then 9⌘ 2 D(x0 ) with high probability on .
Compressed Sensing Setting Random matrix: 2 RP ⇥N , Sparse vectors: J = || · ||1 . Theorem: Let s = ||x0 ||0 . If i,j ⇠ N (0, 1), i.i.d. [Rudelson, Vershynin 2006] [Chandrasekaran et al. 2011] P > 2s log (N/s) ¯ Then 9⌘ 2 D(x0 ) with high probability on Low-rank matrices: J = || · ||⇤ . Theorem: Let r = rank(x0 ). If . [Chandrasekaran et al. 2011] x0 2 RN1 ⇥N2 P > 3r(N1 + N2 r) ¯ Then 9⌘ 2 D(x0 ) with high probability on ! Similar results for || · ||1,2 , || · ||1 . .
Minimal-norm Certificate ⌘ 2 D(x0 ) =) ⇢ ⌘ = ⇤q ProjT (⌘) = e T = T x0 e = ex0
Minimal-norm Certificate ⌘ 2 D(x0 ) =) ⇢ ⌘ = ⇤q ProjT (⌘) = e Minimal-norm pre-certificate: ⌘0 = T = T x0 e = ex0 argmin ⌘= ⇤ q,⌘ T =e ||q||
Minimal-norm Certificate ⌘ 2 D(x0 ) =) ⇢ ⌘ = ⇤q ProjT (⌘) = e Minimal-norm pre-certificate: ⌘0 = Proposition: One has T = T x0 e = ex0 argmin ⌘= ⌘0 = ( ⇤ q,⌘ + T T =e )⇤ e ||q||
Minimal-norm Certificate ⌘ 2 D(x0 ) =) ⇢ ⌘ = ⇤q ProjT (⌘) = e Minimal-norm pre-certificate: ⌘0 = argmin ⌘= One has ⌘0 = ( ¯ If ⌘0 2 D(x0 ) and ⇤ q,⌘ + T T =e ||q|| )⇤ e ⇠ ||w||, Proposition: Theorem: T = T x0 e = ex0 the unique solution x? of P (y) for y = x0 + w satisfies Tx ? = T x 0 and ||x? x0 || = O(||w||) [Vaiter et al. 2013]
Minimal-norm Certificate ⌘ 2 D(x0 ) =) ⇢ ⌘ = ⇤q ProjT (⌘) = e Minimal-norm pre-certificate: ⌘0 = argmin ⌘= One has ⌘0 = ( ¯ If ⌘0 2 D(x0 ) and ⇤ q,⌘ + T T =e ||q|| )⇤ e ⇠ ||w||, Proposition: Theorem: T = T x0 e = ex0 the unique solution x? of P (y) for y = x0 + w satisfies Tx ? = T x 0 and ||x? x0 || = O(||w||) [Vaiter et al. 2013] [Fuchs 2004]: J = || · ||1 . [Vaiter et al. 2011]: J = ||D⇤ · ||1 . [Bach 2008]: J = || · ||1,2 and J = || · ||⇤ .
Compressed Sensing Setting Random matrix: 2 RP ⇥N , Sparse vectors: J = || · ||1 . Theorem: Let s = ||x0 ||0 . If i,j ⇠ N (0, 1), i.i.d. [Wainwright 2009] [Dossal et al. 2011] P > 2s log(N ) ¯ Then ⌘0 2 D( x0 ) wi th hi g h prob a b i l i ty on .
Compressed Sensing Setting Random matrix: 2 RP ⇥N , i,j Sparse vectors: J = || · ||1 . ⇠ N (0, 1), i.i.d. [Wainwright 2009] [Dossal et al. 2011] Theorem: Let s = ||x0 ||0 . If P > 2s log(N ) ¯ Then ⌘0 2 D( x0 ) wi th hi g h prob a b i l i ty on Phase transitions: L2 stability P ⇠ 2s log(N/s) vs. . Model stability P ⇠ 2s log(N )
Compressed Sensing Setting Random matrix: 2 RP ⇥N , i,j Sparse vectors: J = || · ||1 . ⇠ N (0, 1), i.i.d. [Wainwright 2009] [Dossal et al. 2011] Theorem: Let s = ||x0 ||0 . If P > 2s log(N ) ¯ Then ⌘0 2 D( x0 ) wi th hi g h prob a b i l i ty on Phase transitions: L2 stability P ⇠ 2s log(N/s) vs. . Model stability ! Similar results for || · ||1,2 , || · ||⇤ , || · ||1 . P ⇠ 2s log(N )
Compressed Sensing Setting Random matrix: 2 RP ⇥N , i,j Sparse vectors: J = || · ||1 . ⇠ N (0, 1), i.i.d. [Wainwright 2009] [Dossal et al. 2011] Theorem: Let s = ||x0 ||0 . If P > 2s log(N ) ¯ Then ⌘0 2 D( x0 ) wi th hi g h prob a b i l i ty on Phase transitions: L2 stability P ⇠ 2s log(N/s) vs. . Model stability ! Similar results for || · ||1,2 , || · ||⇤ , || · ||1 . P ⇠ 2s log(N ) ! Not using RIP technics (non-uniform result on x0 ).
1-D Sparse Spikes Deconvolution ⇥x = xi (· i) x0 i J(x) = ||x||1 Increasing : reduces correlation. reduces resolution. x0
1-D Sparse Spikes Deconvolution ⇥x = xi (· x0 i) i J(x) = ||x||1 Increasing : reduces correlation. reduces resolution. x0 ||⌘0,I c ||1 2 1 0 10 20 I = {j x0 (j) 6= 0} ||⌘0,I c ||1 < 1 () ¯ ⌘0 2 D(x0 ) () support recovery.
Conclusion Gauges: encode linear models as singular points.
Conclusion Gauges: encode linear models as singular points. Performance measures L2 error model di↵erent CS guarantees
Conclusion Gauges: encode linear models as singular points. Performance measures L2 error model di↵erent CS guarantees Specific certificate ⌘0 .
Conclusion Gauges: encode linear models as singular points. Performance measures L2 error model di↵erent CS guarantees Specific certificate ⌘0 . Open problems: – Approximate model recovery Tx? ⇡ Tx0 . – CS performance with complicated gauges (e.g. TV).

More Related Content

PDF
Proximal Splitting and Optimal Transport
byGabriel Peyré
 
PDF
Low Complexity Regularization of Inverse Problems - Course #3 Proximal Splitt...
byGabriel Peyré
 
PDF
Low Complexity Regularization of Inverse Problems - Course #2 Recovery Guaran...
byGabriel Peyré
 
PDF
Mesh Processing Course : Active Contours
byGabriel Peyré
 
PDF
Signal Processing Course : Convex Optimization
byGabriel Peyré
 
PDF
Low Complexity Regularization of Inverse Problems - Course #1 Inverse Problems
byGabriel Peyré
 
PDF
Model Selection with Piecewise Regular Gauges
byGabriel Peyré
 
PDF
Signal Processing Course : Inverse Problems Regularization
byGabriel Peyré
 
Proximal Splitting and Optimal Transport
byGabriel Peyré
 
Low Complexity Regularization of Inverse Problems - Course #3 Proximal Splitt...
byGabriel Peyré
 
Low Complexity Regularization of Inverse Problems - Course #2 Recovery Guaran...
byGabriel Peyré
 
Mesh Processing Course : Active Contours
byGabriel Peyré
 
Signal Processing Course : Convex Optimization
byGabriel Peyré
 
Low Complexity Regularization of Inverse Problems - Course #1 Inverse Problems
byGabriel Peyré
 
Model Selection with Piecewise Regular Gauges
byGabriel Peyré
 
Signal Processing Course : Inverse Problems Regularization
byGabriel Peyré
 

What's hot

PDF
Geodesic Method in Computer Vision and Graphics
byGabriel Peyré
 
PDF
Mesh Processing Course : Multiresolution
byGabriel Peyré
 
PDF
Learning Sparse Representation
byGabriel Peyré
 
PDF
Mesh Processing Course : Mesh Parameterization
byGabriel Peyré
 
PDF
Lecture 2: linear SVM in the dual
byStéphane Canu
 
PDF
A series of maximum entropy upper bounds of the differential entropy
byFrank Nielsen
 
PDF
Classification with mixtures of curved Mahalanobis metrics
byFrank Nielsen
 
PDF
Adaptive Signal and Image Processing
byGabriel Peyré
 
PDF
Bregman divergences from comparative convexity
byFrank Nielsen
 
PDF
Signal Processing Course : Sparse Regularization of Inverse Problems
byGabriel Peyré
 
PDF
Open GL 04 linealgos
byRoziq Bahtiar
 
PDF
Lecture5 kernel svm
byStéphane Canu
 
PDF
The dual geometry of Shannon information
byFrank Nielsen
 
PDF
Image Processing 3
byjainatin
 
PDF
Mesh Processing Course : Geodesic Sampling
byGabriel Peyré
 
PDF
Mesh Processing Course : Geodesics
byGabriel Peyré
 
PDF
Lecture 1: linear SVM in the primal
byStéphane Canu
 
PDF
Lecture3 linear svm_with_slack
byStéphane Canu
 
PDF
L. Jonke - A Twisted Look on Kappa-Minkowski: U(1) Gauge Theory
bySEENET-MTP
 
PDF
Tensor Completion for PDEs with uncertain coefficients and Bayesian Update te...
byAlexander Litvinenko
 
Geodesic Method in Computer Vision and Graphics
byGabriel Peyré
 
Mesh Processing Course : Multiresolution
byGabriel Peyré
 
Learning Sparse Representation
byGabriel Peyré
 
Mesh Processing Course : Mesh Parameterization
byGabriel Peyré
 
Lecture 2: linear SVM in the dual
byStéphane Canu
 
A series of maximum entropy upper bounds of the differential entropy
byFrank Nielsen
 
Classification with mixtures of curved Mahalanobis metrics
byFrank Nielsen
 
Adaptive Signal and Image Processing
byGabriel Peyré
 
Bregman divergences from comparative convexity
byFrank Nielsen
 
Signal Processing Course : Sparse Regularization of Inverse Problems
byGabriel Peyré
 
Open GL 04 linealgos
byRoziq Bahtiar
 
Lecture5 kernel svm
byStéphane Canu
 
The dual geometry of Shannon information
byFrank Nielsen
 
Image Processing 3
byjainatin
 
Mesh Processing Course : Geodesic Sampling
byGabriel Peyré
 
Mesh Processing Course : Geodesics
byGabriel Peyré
 
Lecture 1: linear SVM in the primal
byStéphane Canu
 
Lecture3 linear svm_with_slack
byStéphane Canu
 
L. Jonke - A Twisted Look on Kappa-Minkowski: U(1) Gauge Theory
bySEENET-MTP
 
Tensor Completion for PDEs with uncertain coefficients and Bayesian Update te...
byAlexander Litvinenko
 

Similar to Low Complexity Regularization of Inverse Problems

PDF
離散値ベクトル再構成手法とその通信応用
byRyo Hayakawa
 
PDF
Defense_Talk
bycastanan2
 
PDF
NIPS2009: Sparse Methods for Machine Learning: Theory and Algorithms
byzukun
 
PDF
CVPR2010: Sparse Coding and Dictionary Learning for Image Analysis: Part 1: S...
byzukun
 
PDF
Tuto cvpr part1
byzukun
 
PDF
omp-and-k-svd - Gdc2013
byManchor Ko
 
PDF
23
bysunil raj kumar
 
PDF
1108.1170
byTomasz Waszczyk
 
PDF
SURF 2012 Final Report(1)
byEric Zhang
 
PPTX
C&s sparse june_2010
bympbchina
 
PDF
QMC: Operator Splitting Workshop, Thresholdings, Robustness, and Generalized ...
byThe Statistical and Applied Mathematical Sciences Institute
 
PDF
Linear regression
byZoya Bylinskii
 
PDF
Nonconvex Compressed Sensing with the Sum-of-Squares Method
byTasuku Soma
 
PDF
compressed-sensing
bySteve Dias da Cruz
 
PPTX
1 d,2d laplace inversion of lr nmr
byAdam Lee Perelman
 
PPTX
Solving Poisson Equation using Conjugate Gradient Method and its implementation
byJongsu "Liam" Kim
 
PDF
Injecting image priors into Learnable Compressive Subsampling
byMartino Ferrari
 
PDF
Robust Sparse Analysis Recovery
byGabriel Peyré
 
PDF
SIGGRAPHASIA2012_Talk
byChih-Tsung Shen
 
PDF
Matrix Padding Method for Sparse Signal Reconstruction
byCSCJournals
 
離散値ベクトル再構成手法とその通信応用
byRyo Hayakawa
 
Defense_Talk
bycastanan2
 
NIPS2009: Sparse Methods for Machine Learning: Theory and Algorithms
byzukun
 
CVPR2010: Sparse Coding and Dictionary Learning for Image Analysis: Part 1: S...
byzukun
 
Tuto cvpr part1
byzukun
 
omp-and-k-svd - Gdc2013
byManchor Ko
 
23
bysunil raj kumar
 
1108.1170
byTomasz Waszczyk
 
SURF 2012 Final Report(1)
byEric Zhang
 
C&s sparse june_2010
bympbchina
 
QMC: Operator Splitting Workshop, Thresholdings, Robustness, and Generalized ...
byThe Statistical and Applied Mathematical Sciences Institute
 
Linear regression
byZoya Bylinskii
 
Nonconvex Compressed Sensing with the Sum-of-Squares Method
byTasuku Soma
 
compressed-sensing
bySteve Dias da Cruz
 
1 d,2d laplace inversion of lr nmr
byAdam Lee Perelman
 
Solving Poisson Equation using Conjugate Gradient Method and its implementation
byJongsu "Liam" Kim
 
Injecting image priors into Learnable Compressive Subsampling
byMartino Ferrari
 
Robust Sparse Analysis Recovery
byGabriel Peyré
 
SIGGRAPHASIA2012_Talk
byChih-Tsung Shen
 
Matrix Padding Method for Sparse Signal Reconstruction
byCSCJournals
 

More from Gabriel Peyré

PDF
Mesh Processing Course : Introduction
byGabriel Peyré
 
PDF
Mesh Processing Course : Differential Calculus
byGabriel Peyré
 
PDF
Signal Processing Course : Theory for Sparse Recovery
byGabriel Peyré
 
PDF
Signal Processing Course : Presentation of the Course
byGabriel Peyré
 
PDF
Signal Processing Course : Orthogonal Bases
byGabriel Peyré
 
PDF
Signal Processing Course : Fourier
byGabriel Peyré
 
PDF
Signal Processing Course : Denoising
byGabriel Peyré
 
PDF
Signal Processing Course : Compressed Sensing
byGabriel Peyré
 
PDF
Signal Processing Course : Approximation
byGabriel Peyré
 
PDF
Signal Processing Course : Wavelets
byGabriel Peyré
 
PDF
Sparsity and Compressed Sensing
byGabriel Peyré
 
PDF
Optimal Transport in Imaging Sciences
byGabriel Peyré
 
PDF
An Introduction to Optimal Transport
byGabriel Peyré
 
PDF
A Review of Proximal Methods, with a New One
byGabriel Peyré
 
Mesh Processing Course : Introduction
byGabriel Peyré
 
Mesh Processing Course : Differential Calculus
byGabriel Peyré
 
Signal Processing Course : Theory for Sparse Recovery
byGabriel Peyré
 
Signal Processing Course : Presentation of the Course
byGabriel Peyré
 
Signal Processing Course : Orthogonal Bases
byGabriel Peyré
 
Signal Processing Course : Fourier
byGabriel Peyré
 
Signal Processing Course : Denoising
byGabriel Peyré
 
Signal Processing Course : Compressed Sensing
byGabriel Peyré
 
Signal Processing Course : Approximation
byGabriel Peyré
 
Signal Processing Course : Wavelets
byGabriel Peyré
 
Sparsity and Compressed Sensing
byGabriel Peyré
 
Optimal Transport in Imaging Sciences
byGabriel Peyré
 
An Introduction to Optimal Transport
byGabriel Peyré
 
A Review of Proximal Methods, with a New One
byGabriel Peyré
 

Recently uploaded

PDF
1. BITA Introduction Slides Oct 2526.pdf
byMark Kor
 
PDF
Lehigh University Eng. Programs for Thailand
bycama23
 
PDF
UV Visible Spectroscopy M.Pharm Notes PPT file, Pharmacy
bySaurabh Dubey
 
PPTX
Becoming a Senior Student Week 4 Term 4 10CLA.pptx
bymansk2
 
PDF
47 ĐỀ CHÍNH THỨC THI CHỌN HỌC SINH GIỎI CÁC TỈNH MÔN TIẾNG ANH LỚP 8 THCS NĂM...
byNguyen Thanh Tu Collection
 
PPTX
GDG CU Google Cloud Study Jams 2025 Kickoff.pptx
byNamVr
 
DOCX
PHYSIOLOGY NOTES - Dr. SUDHADEVI SADANANDAN
byDr. Sudhadevi Sadanandan
 
PPTX
Bram Stoker's Dracula. Gothic novel characteristics
byRaquel FC
 
PPTX
Environmental Degradation and Pollution
bySheila Mae Ellima
 
PDF
Heading Off 'Fakes' in the Academic Publishing Space
byShalin Hai-Jew
 
PDF
Hit The Homerun Prelims- A U25 sports quiz of Jigisha 4.0 organized by Pragya...
byPragya - UEM Kolkata Quiz Club
 
PPTX
Quiz-O-Force Diwali Quiz Final Round.pptx
bySourav Kr Podder
 
PPTX
THE INDIA QUIZ 14th AUGUST-FINALS R-1.pptx
byPrometheans Quiz Club
 
PPTX
Essential Elements of a Valid Contract.pptx
byKeerthana Chinnathambi
 
PDF
Science, Education and Innovations in the Context of Modern Problems, Issue 1...
byRahilNecef
 
PPTX
Mary Shelley's Frankenstein. Gothic novel characteristics.
byRaquel FC
 
PPTX
Prometheans Gyanotsav quiz - the mixed bag
byPrometheans Quiz Club
 
PPTX
How to Create an Employee Record in Odoo 18 Employee
byCeline George
 
PPTX
Composition and characteristics of blood
byManarat International University
 
PPTX
Neurodevelopmental Learning Needs .pptx
byglungelo06
 
1. BITA Introduction Slides Oct 2526.pdf
byMark Kor
 
Lehigh University Eng. Programs for Thailand
bycama23
 
UV Visible Spectroscopy M.Pharm Notes PPT file, Pharmacy
bySaurabh Dubey
 
Becoming a Senior Student Week 4 Term 4 10CLA.pptx
bymansk2
 
47 ĐỀ CHÍNH THỨC THI CHỌN HỌC SINH GIỎI CÁC TỈNH MÔN TIẾNG ANH LỚP 8 THCS NĂM...
byNguyen Thanh Tu Collection
 
GDG CU Google Cloud Study Jams 2025 Kickoff.pptx
byNamVr
 
PHYSIOLOGY NOTES - Dr. SUDHADEVI SADANANDAN
byDr. Sudhadevi Sadanandan
 
Bram Stoker's Dracula. Gothic novel characteristics
byRaquel FC
 
Environmental Degradation and Pollution
bySheila Mae Ellima
 
Heading Off 'Fakes' in the Academic Publishing Space
byShalin Hai-Jew
 
Hit The Homerun Prelims- A U25 sports quiz of Jigisha 4.0 organized by Pragya...
byPragya - UEM Kolkata Quiz Club
 
Quiz-O-Force Diwali Quiz Final Round.pptx
bySourav Kr Podder
 
THE INDIA QUIZ 14th AUGUST-FINALS R-1.pptx
byPrometheans Quiz Club
 
Essential Elements of a Valid Contract.pptx
byKeerthana Chinnathambi
 
Science, Education and Innovations in the Context of Modern Problems, Issue 1...
byRahilNecef
 
Mary Shelley's Frankenstein. Gothic novel characteristics.
byRaquel FC
 
Prometheans Gyanotsav quiz - the mixed bag
byPrometheans Quiz Club
 
How to Create an Employee Record in Odoo 18 Employee
byCeline George
 
Composition and characteristics of blood
byManarat International University
 
Neurodevelopmental Learning Needs .pptx
byglungelo06
 

Low Complexity Regularization of Inverse Problems

  • 1.
    Low Complexity Regularization of InverseProblems Gabriel Peyré Joint works with: Samuel Vaiter Jalal Fadili Charles Dossal Mohammad Golbabaee VISI www.numerical-tours.com N
  • 2.
    Overview • Compressed Sensingand Inverse Problems • Convex Regularization with Gauges • Performance Guarantees
  • 3.
    Single Pixel Camera(Rice) x0 ˜
  • 4.
    Single Pixel Camera(Rice) x0 ˜ y[i] = hx0 , 'i i P measures N micro-mirrors
  • 5.
    Single Pixel Camera(Rice) x0 ˜ y[i] = hx0 , 'i i P measures P/N = 1 N micro-mirrors P/N = 0.16 P/N = 0.02
  • 6.
    CS Hardware Model ˜ CSis about designing hardware: input signals f L2 (R2 ). Physical hardware resolution limit: target resolution f 2 x0 2 L ˜ array resolution CS hardware x0 2 R N micro mirrors RN . y 2 RP
  • 7.
    CS Hardware Model ˜ CSis about designing hardware: input signals f L2 (R2 ). Physical hardware resolution limit: target resolution f x0 2 L ˜ array resolution x0 2 R N micro mirrors y 2 RP CS hardware , , ... 2 RN . , Operator x0
  • 8.
    Inverse Problems Recovering x0RN from noisy observations y = x 0 + w 2 RP
  • 9.
    Inverse Problems Recovering x0RN from noisy observations y = x 0 + w 2 RP Examples: Inpainting, super-resolution, compressed-sensing x0 x0
  • 10.
    Inverse Problem Regularization Observations:y = x0 + w 2 RP . Estimator: x(y) depends only on observations y parameter
  • 11.
    Inverse Problem Regularization Observations:y = x0 + w 2 RP . Estimator: x(y) depends only on observations y parameter Example: variational methods 1 x(y) 2 argmin ||y x||2 + J(x) x2RN 2 Data fidelity Regularity
  • 12.
    Inverse Problem Regularization Observations:y = x0 + w 2 RP . Estimator: x(y) depends only on observations y parameter Example: variational methods 1 x(y) 2 argmin ||y x||2 + J(x) x2RN 2 Data fidelity Regularity Performance analysis: ! Criteria on (x0 , ||w||, ) to ensure L2 stability ||x(y) x0 || = O(||w||) Model stability (e.g. spikes location)
  • 13.
    Overview • Compressed Sensingand Inverse Problems • Convex Regularization with Gauges • Performance Guarantees
  • 14.
    Union of LinearModels for Data Processing Union of models: T 2 T linear spaces. Synthesis sparsity: T Coe cients x Image x
  • 15.
    Union of LinearModels for Data Processing Union of models: T 2 T linear spaces. Synthesis sparsity: Structured sparsity: T Coe cients x Image x
  • 16.
    Union of LinearModels for Data Processing Union of models: T 2 T linear spaces. Synthesis sparsity: Structured sparsity: T Coe cients x Image x D Analysis sparsity: Image x Gradient D⇤ x
  • 17.
    Union of LinearModels for Data Processing Union of models: T 2 T linear spaces. Synthesis sparsity: Structured sparsity: T Coe cients x Analysis sparsity: Image x D Low-rank: Image x Gradient D⇤ x S1,· Multi-spectral imaging: Pr xi,· = j=1 Ai,j Sj,· S2,· x S3,·
  • 18.
    Gauges for Unionof Linear Models Gauge: J :R N !R + Convex 8 ↵ 2 R+ , J(↵x) = ↵J(x)
  • 19.
    Gauges for Unionof Linear Models Gauge: J :R N !R + Convex 8 ↵ 2 R+ , J(↵x) = ↵J(x) Piecewise regular ball , Union of linear models (T )T 2T x J(x) = ||x||1 T T = sparse vectors
  • 20.
    Gauges for Unionof Linear Models Gauge: J :R N !R + Convex 8 ↵ 2 R+ , J(↵x) = ↵J(x) Piecewise regular ball , Union of linear models (T )T 2T T0 x0 x J(x) = ||x||1 T T = sparse vectors
  • 21.
    Gauges for Unionof Linear Models Gauge: J :R N !R Convex 8 ↵ 2 R+ , J(↵x) = ↵J(x) + Piecewise regular ball , Union of linear models (T )T 2T T T0 x0 x J(x) = ||x||1 T T = sparse vectors x T0 x |x1 |+||x2,3 || T = block sparse vectors 0
  • 22.
    Gauges for Unionof Linear Models Gauge: J :R N !R Convex 8 ↵ 2 R+ , J(↵x) = ↵J(x) + Piecewise regular ball , Union of linear models (T )T 2T T T0 x0 x J(x) = ||x||1 T T = sparse vectors x T x |x1 |+||x2,3 || T = block sparse vectors 0 x 0 J(x) = ||x||⇤ T = low-rank matrices
  • 23.
    Gauges for Unionof Linear Models Gauge: J :R N !R Convex 8 ↵ 2 R+ , J(↵x) = ↵J(x) + Piecewise regular ball , Union of linear models (T )T 2T T T0 x0 x J(x) = ||x||1 T T = sparse vectors T0 x T x |x1 |+||x2,3 || T = block sparse vectors 0 x x x0 0 J(x) = ||x||⇤ T = low-rank matrices J(x) = ||x||1 T = antisparse vectors
  • 24.
    Subdifferentials and Models @J(x)= {⌘ 8 y, J(y) > J(x)+h⌘, y xi} |x|
  • 25.
    Subdifferentials and Models @J(x)= {⌘ 8 y, J(y) > J(x)+h⌘, y |x| xi} Example: J(x) = ||x||1 ⇢ supp(⌘) = I, @||x||1 = ⌘ 8 j 2 I, |⌘j | 6 1 / I = supp(x) = {i xi 6= 0} @J(x) 0 x
  • 26.
    Subdifferentials and Models @J(x)= {⌘ 8 y, J(y) > J(x)+h⌘, y |x| xi} Example: J(x) = ||x||1 ⇢ supp(⌘) = I, @||x||1 = ⌘ 8 j 2 I, |⌘j | 6 1 / I = supp(x) = {i xi 6= 0} Tx = {⌘ supp(⌘) = I} Definition: Tx = VectHull(@J(x))? @J(x) 0 x Tx
  • 27.
    Subdifferentials and Models @J(x)= {⌘ 8 y, J(y) > J(x)+h⌘, y |x| xi} Example: J(x) = ||x||1 ⇢ supp(⌘) = I, @||x||1 = ⌘ 8 j 2 I, |⌘j | 6 1 / @J(x) 0 I = supp(x) = {i xi 6= 0} Tx Tx = {⌘ supp(⌘) = I} ex = sign(x) Definition: Tx = VectHull(@J(x))? ⌘ 2 @J(x) ex x =) ProjTx (⌘) = ex
  • 28.
    Examples `1 sparsity: J(x)= ||x||1 ex = sign(x) x @J(x) x 0 Tx = {z supp(z) ⇢ supp(x)}
  • 29.
    Examples `1 sparsity: J(x)= ||x||1 ex = sign(x) Tx = {z supp(z) ⇢ supp(x)} P Structured sparsity: J(x) = b ||xb || N (a) = a/||a|| ex = (N (xb ))b2B Tx = {z supp(z) ⇢ supp(x)} x @J(x) x 0 x @J(x) x 0
  • 30.
    Examples `1 sparsity: J(x)= ||x||1 ex = sign(x) Tx = {z supp(z) ⇢ supp(x)} P Structured sparsity: J(x) = b ||xb || N (a) = a/||a|| ex = (N (xb ))b2B Tx = {z supp(z) ⇢ supp(x)} Nuclear norm: J(x) = ||x||⇤ ex = U V x @J(x) x 0 ⇤ x x = U ⇤V ⇤ SVD: ⇤ Tx = {z U? zV? = 0} @J(x) x 0 x @J(x)
  • 31.
    Examples `1 sparsity: J(x)= ||x||1 ex = sign(x) Tx = {z supp(z) ⇢ supp(x)} P Structured sparsity: J(x) = b ||xb || N (a) = a/||a|| ex = (N (xb ))b2B Tx = {z supp(z) ⇢ supp(x)} Nuclear norm: J(x) = ||x||⇤ ex = U V ⇤ x = U ⇤V ⇤ SVD: ⇤ Tx = {z U? zV? = 0} I = {i |xi | = ||x||1 } Anti-sparsity: J(x) = ||x||1 Tx = {y yI / sign(xI )} ex = |I| 1 sign(x) x @J(x) x 0 x @J(x) @J(x) x 0 x @J(x) x x 0
  • 32.
    Overview • Compressed Sensingand Inverse Problems • Convex Regularization with Gauges • Performance Guarantees
  • 33.
    Dual Certificate andL2 Stability Noiseless recovery: min J(x) x= x0 (P0 ) x? x= x0
  • 34.
    Dual Certificate andL2 Stability Noiseless recovery: min J(x) x= x0 (P0 ) Proposition: x0 solution of (P0 ) () 9 ⌘ 2 D(x0 ) Dual certificates: D(x0 ) = Im( ⇤ ⌘ x? ) @J(x0 ) @J(x0 ) x= x0
  • 35.
    Dual Certificate andL2 Stability Noiseless recovery: min J(x) x= x0 (P0 ) Proposition: x0 solution of (P0 ) () 9 ⌘ 2 D(x0 ) Dual certificates: D(x0 ) = Im( ¯ Tight dual certificates: D(x0 ) = Im( ⇤ ⌘ @J(x0 ) x? ) @J(x0 ) ⇤ ) ri(@J(x0 )) x= x0
  • 36.
    Dual Certificate andL2 Stability Noiseless recovery: min J(x) x= x0 (P0 ) Proposition: x0 solution of (P0 ) () 9 ⌘ 2 D(x0 ) Dual certificates: D(x0 ) = Im( ¯ Tight dual certificates: D(x0 ) = Im( Theorem: ¯ If 9 ⌘ 2 D(x0 ), for ⌘ @J(x0 ) x? x= x0 ⇤ ) @J(x0 ) ⇤ ) ri(@J(x0 )) [Fadili et al. 2013] ⇠ ||w|| one has ||x? x0 || = O(||w||)
  • 37.
    Dual Certificate andL2 Stability Noiseless recovery: min J(x) x= x0 (P0 ) Proposition: x0 solution of (P0 ) () 9 ⌘ 2 D(x0 ) Dual certificates: D(x0 ) = Im( ¯ Tight dual certificates: D(x0 ) = Im( Theorem: ¯ If 9 ⌘ 2 D(x0 ), for ⌘ @J(x0 ) x? x= x0 ⇤ ) @J(x0 ) ⇤ ) ri(@J(x0 )) [Fadili et al. 2013] ⇠ ||w|| one has ||x? x0 || = O(||w||) [Grassmair, Haltmeier, Scherzer 2010]: J = || · ||1 . [Grassmair 2012]: J(x? x0 ) = O(||w||).
  • 38.
    Compressed Sensing Setting Randommatrix: 2 RP ⇥N , i,j ⇠ N (0, 1), i.i.d.
  • 39.
    Compressed Sensing Setting Randommatrix: 2 RP ⇥N , Sparse vectors: J = || · ||1 . Theorem: Let s = ||x0 ||0 . If i,j ⇠ N (0, 1), i.i.d. [Rudelson, Vershynin 2006] [Chandrasekaran et al. 2011] P > 2s log (N/s) ¯ Then 9⌘ 2 D(x0 ) with high probability on .
  • 40.
    Compressed Sensing Setting Randommatrix: 2 RP ⇥N , Sparse vectors: J = || · ||1 . Theorem: Let s = ||x0 ||0 . If i,j ⇠ N (0, 1), i.i.d. [Rudelson, Vershynin 2006] [Chandrasekaran et al. 2011] P > 2s log (N/s) ¯ Then 9⌘ 2 D(x0 ) with high probability on Low-rank matrices: J = || · ||⇤ . Theorem: Let r = rank(x0 ). If . [Chandrasekaran et al. 2011] x0 2 RN1 ⇥N2 P > 3r(N1 + N2 r) ¯ Then 9⌘ 2 D(x0 ) with high probability on .
  • 41.
    Compressed Sensing Setting Randommatrix: 2 RP ⇥N , Sparse vectors: J = || · ||1 . Theorem: Let s = ||x0 ||0 . If i,j ⇠ N (0, 1), i.i.d. [Rudelson, Vershynin 2006] [Chandrasekaran et al. 2011] P > 2s log (N/s) ¯ Then 9⌘ 2 D(x0 ) with high probability on Low-rank matrices: J = || · ||⇤ . Theorem: Let r = rank(x0 ). If . [Chandrasekaran et al. 2011] x0 2 RN1 ⇥N2 P > 3r(N1 + N2 r) ¯ Then 9⌘ 2 D(x0 ) with high probability on ! Similar results for || · ||1,2 , || · ||1 . .
  • 42.
    Minimal-norm Certificate ⌘ 2D(x0 ) =) ⇢ ⌘ = ⇤q ProjT (⌘) = e T = T x0 e = ex0
  • 43.
    Minimal-norm Certificate ⌘ 2D(x0 ) =) ⇢ ⌘ = ⇤q ProjT (⌘) = e Minimal-norm pre-certificate: ⌘0 = T = T x0 e = ex0 argmin ⌘= ⇤ q,⌘ T =e ||q||
  • 44.
    Minimal-norm Certificate ⌘ 2D(x0 ) =) ⇢ ⌘ = ⇤q ProjT (⌘) = e Minimal-norm pre-certificate: ⌘0 = Proposition: One has T = T x0 e = ex0 argmin ⌘= ⌘0 = ( ⇤ q,⌘ + T T =e )⇤ e ||q||
  • 45.
    Minimal-norm Certificate ⌘ 2D(x0 ) =) ⇢ ⌘ = ⇤q ProjT (⌘) = e Minimal-norm pre-certificate: ⌘0 = argmin ⌘= One has ⌘0 = ( ¯ If ⌘0 2 D(x0 ) and ⇤ q,⌘ + T T =e ||q|| )⇤ e ⇠ ||w||, Proposition: Theorem: T = T x0 e = ex0 the unique solution x? of P (y) for y = x0 + w satisfies Tx ? = T x 0 and ||x? x0 || = O(||w||) [Vaiter et al. 2013]
  • 46.
    Minimal-norm Certificate ⌘ 2D(x0 ) =) ⇢ ⌘ = ⇤q ProjT (⌘) = e Minimal-norm pre-certificate: ⌘0 = argmin ⌘= One has ⌘0 = ( ¯ If ⌘0 2 D(x0 ) and ⇤ q,⌘ + T T =e ||q|| )⇤ e ⇠ ||w||, Proposition: Theorem: T = T x0 e = ex0 the unique solution x? of P (y) for y = x0 + w satisfies Tx ? = T x 0 and ||x? x0 || = O(||w||) [Vaiter et al. 2013] [Fuchs 2004]: J = || · ||1 . [Vaiter et al. 2011]: J = ||D⇤ · ||1 . [Bach 2008]: J = || · ||1,2 and J = || · ||⇤ .
  • 47.
    Compressed Sensing Setting Randommatrix: 2 RP ⇥N , Sparse vectors: J = || · ||1 . Theorem: Let s = ||x0 ||0 . If i,j ⇠ N (0, 1), i.i.d. [Wainwright 2009] [Dossal et al. 2011] P > 2s log(N ) ¯ Then ⌘0 2 D( x0 ) wi th hi g h prob a b i l i ty on .
  • 48.
    Compressed Sensing Setting Randommatrix: 2 RP ⇥N , i,j Sparse vectors: J = || · ||1 . ⇠ N (0, 1), i.i.d. [Wainwright 2009] [Dossal et al. 2011] Theorem: Let s = ||x0 ||0 . If P > 2s log(N ) ¯ Then ⌘0 2 D( x0 ) wi th hi g h prob a b i l i ty on Phase transitions: L2 stability P ⇠ 2s log(N/s) vs. . Model stability P ⇠ 2s log(N )
  • 49.
    Compressed Sensing Setting Randommatrix: 2 RP ⇥N , i,j Sparse vectors: J = || · ||1 . ⇠ N (0, 1), i.i.d. [Wainwright 2009] [Dossal et al. 2011] Theorem: Let s = ||x0 ||0 . If P > 2s log(N ) ¯ Then ⌘0 2 D( x0 ) wi th hi g h prob a b i l i ty on Phase transitions: L2 stability P ⇠ 2s log(N/s) vs. . Model stability ! Similar results for || · ||1,2 , || · ||⇤ , || · ||1 . P ⇠ 2s log(N )
  • 50.
    Compressed Sensing Setting Randommatrix: 2 RP ⇥N , i,j Sparse vectors: J = || · ||1 . ⇠ N (0, 1), i.i.d. [Wainwright 2009] [Dossal et al. 2011] Theorem: Let s = ||x0 ||0 . If P > 2s log(N ) ¯ Then ⌘0 2 D( x0 ) wi th hi g h prob a b i l i ty on Phase transitions: L2 stability P ⇠ 2s log(N/s) vs. . Model stability ! Similar results for || · ||1,2 , || · ||⇤ , || · ||1 . P ⇠ 2s log(N ) ! Not using RIP technics (non-uniform result on x0 ).
  • 51.
    1-D Sparse SpikesDeconvolution ⇥x = xi (· i) x0 i J(x) = ||x||1 Increasing : reduces correlation. reduces resolution. x0
  • 52.
    1-D Sparse SpikesDeconvolution ⇥x = xi (· x0 i) i J(x) = ||x||1 Increasing : reduces correlation. reduces resolution. x0 ||⌘0,I c ||1 2 1 0 10 20 I = {j x0 (j) 6= 0} ||⌘0,I c ||1 < 1 () ¯ ⌘0 2 D(x0 ) () support recovery.
  • 53.
    Conclusion Gauges: encode linearmodels as singular points.
  • 54.
    Conclusion Gauges: encode linearmodels as singular points. Performance measures L2 error model di↵erent CS guarantees
  • 55.
    Conclusion Gauges: encode linearmodels as singular points. Performance measures L2 error model di↵erent CS guarantees Specific certificate ⌘0 .
  • 56.
    Conclusion Gauges: encode linearmodels as singular points. Performance measures L2 error model di↵erent CS guarantees Specific certificate ⌘0 . Open problems: – Approximate model recovery Tx? ⇡ Tx0 . – CS performance with complicated gauges (e.g. TV).