Candes.m
From Wikimization
(Difference between revisions)
(16 intermediate revisions not shown.) | |||
Line 1: | Line 1: | ||
+ | This Matlab demonstration of ''compressive sampling'' (<tt>a.k.a.</tt> ''compressed sensing'') by [http://www.acm.caltech.edu/~emmanuel Emmanuel Candès]<br> comes from his [http://www.convexoptimization.com/wikimization/index.php/Optimization_Videos#June_6_2007_.C2.A0Sparsity_and_Incoherence June 6 2007] video on the [[Optimization Videos]] page. | ||
+ | |||
<pre> | <pre> | ||
%Emmanuel Candes, California Institute of Technology, June 6 2007, IMA Summerschool. | %Emmanuel Candes, California Institute of Technology, June 6 2007, IMA Summerschool. | ||
Line 36: | Line 38: | ||
<code>randsample()</code> is from Matlab Statistics Toolbox. | <code>randsample()</code> is from Matlab Statistics Toolbox. | ||
- | Failure modes are reparable by [[Convex Iteration]]. | + | === Revision === |
+ | Failure modes are reparable by [[Convex Iteration]] from [http://www.convexoptimization.com/TOOLS/0976401304.pdf ''Convex Optimization & Euclidean Distance Geometry'', Ch.4.5]: | ||
<pre> | <pre> | ||
%Emmanuel Candes, California Institute of Technology, June 6 2007, IMA Summerschool. | %Emmanuel Candes, California Institute of Technology, June 6 2007, IMA Summerschool. | ||
%Convex Iteration implementation by Jon Dattorro. | %Convex Iteration implementation by Jon Dattorro. | ||
- | %Failures were on 7th consecutive run under SDPT3 after Matlab R2007b startup. CVX version 1.2 (build 656). | ||
- | %Failures were on 4th consecutive run under Sedumi after Matlab R2007b startup. CVX version 1.2 (build 656). | ||
%Failure modes repaired. | %Failure modes repaired. | ||
clear all, close all | clear all, close all |
Current revision
This Matlab demonstration of compressive sampling (a.k.a. compressed sensing) by Emmanuel Candès
comes from his June 6 2007 video on the Optimization Videos page.
%Emmanuel Candes, California Institute of Technology, June 6 2007, IMA Summerschool. %Transcribed by Jon Dattorro. %Fails using SDP solver SDPT3 on 7th consecutive run after Matlab R2007b startup. CVX version 1.2 (build 656). %Fails using SDP solver Sedumi on 4th consecutive run after Matlab R2007b startup. CVX version 1.2 (build 656). clear all, close all n = 512; % Size of signal m = 64; % Number of samples (undersample by a factor 8) k = 0:n-1; t = 0:n-1; F = exp(-i*2*pi*k'*t/n)/sqrt(n); % Fourier matrix freq = randsample(n,m); A = [real(F(freq,:)); imag(F(freq,:))]; % Incomplete Fourier matrix S = 28; support = randsample(n,S); x0 = zeros(n,1); x0(support) = randn(S,1); b = A*x0; % Solve l1 using CVX cvx_quiet(true); %cvx_solver('sedumi'); cvx_begin variable x(n); minimize(norm(x,1)); A*x == b; cvx_end norm(x - x0)/norm(x0) figure, plot(1:n,x0,'b*',1:n,x,'ro'), legend('original','decoded')
Code between cvx_begin
and cvx_end
requires CVX.
randsample()
is from Matlab Statistics Toolbox.
Revision
Failure modes are reparable by Convex Iteration from Convex Optimization & Euclidean Distance Geometry, Ch.4.5:
%Emmanuel Candes, California Institute of Technology, June 6 2007, IMA Summerschool. %Convex Iteration implementation by Jon Dattorro. %Failure modes repaired. clear all, close all n = 512; % Size of signal m = 64; % Number of samples (undersample by a factor 8) k = 0:n-1; t = 0:n-1; F = exp(-i*2*pi*k'*t/n)/sqrt(n); % Fourier matrix freq = randsample(n,m); A = [real(F(freq,:)); imag(F(freq,:))]; % Incomplete Fourier matrix S = 28; support = randsample(n,S); x0 = zeros(n,1); x0(support) = randn(S,1); b = A*x0; cvx_quiet(true); %cvx_solver('sedumi'); %convex iteration y = ones(n,1); while 1 % Solve l0 using CVX and Convex Iteration cvx_begin variable x(n); minimize(norm(y.*x,1)); A*x == b; cvx_end % update search direction y [x_sorted, indices] = sort(abs(x), 'descend'); y = ones(n,1); y(indices(1:S)) = 0; cardx = sum(abs(x) > 1e-6) if cardx <= S, break, end end norm(x - x0)/norm(x0) figure, plot(1:n,x0,'b*',1:n,x,'ro'), legend('original','decoded')