压缩感知Matlab-代码与文档-l1magic-1.11_tomosar压缩感知资源-CSDN文库

共59个文件

m：26个

pdf：8个

eps：7个

压缩感知

Matlab

代码实现

5星 · 超过95%的资源需积分: 32 78 浏览量 2013-10-29 19:44:38 上传评论 3 收藏 509KB ZIP 举报

资源推荐

资源详情

资源评论

收起资源包目录

l1magic-1.11.zip （59个子文件）

l1magic

Optimization

l1qc_logbarrier.m 3KB

l1qc_newton.m 4KB

tvqc_newton.m 5KB

.DS_Store 6KB

l1decode_pd.m 5KB

tvdantzig_newton.m 6KB

l1dantzig_pd.m 7KB

tvqc_logbarrier.m 4KB

tveq_logbarrier.m 3KB

tvdantzig_logbarrier.m 4KB

l1eq_pd.m 6KB

tveq_newton.m 5KB

cgsolve.m 2KB

tvdantzig_example.m 1KB

.DS_Store 12KB

l1dantzig_example.m 955B

l1eq_example.m 1003B

tvqc_example.m 1KB

Notes

l1magic_notes.tex 51KB

l1magic_notes.pdf 272KB

Figs

l1eqexample_signal.pdf 3KB

l1eqexample_signal.eps 11KB

l1eqexample_recovered.eps 11KB

phantom_orig.eps 136KB

phantom_sampling.pdf 6KB

l1eqexample_minl2.pdf 5KB

phantom_sampling.eps 136KB

phantom_backproj.pdf 9KB

l1eqexample_recovered.pdf 4KB

phantom_tv.eps 136KB

CVS

Entries 740B

Repository 18B

Root 41B

phantom_tv.pdf 5KB

l1eqexample_minl2.eps 12KB

phantom_orig.pdf 4KB

phantom_backproj.eps 136KB

l1magic_notes.bbl 4KB

l1magic_notes.log 11KB

.DS_Store 6KB

l1magic.bib 6KB

l1magic_notes.aux 5KB

l1magic_notes.blg 835B

l1qc_example.m 1KB

Data

RandomStates.mat 543B

boats.mat 64KB

.DS_Store 6KB

camera.mat 64KB

tvqc_quantization_example.m 1KB

tveq_phantom_example.m 867B

tveq_example.m 1KB

Measurements

A_fhp.m 576B

At_f.m 718B

.DS_Store 6KB

LineMask.m 832B

At_fhp.m 613B

A_f.m 659B

README 1KB

l1decode_example.m 644B

-magic : Recovery of Sparse Signals

via Convex Programming

Emmanuel Cand`es and Justin Romberg, Caltech

October 2005

1 Seven problems

A recent series of papers [3–8] develops a theory of signal recovery from highly incomplete

information. The central results state that a sparse vector x

∈ R

can be recovered from a

small number of linear measurements b = Ax

∈ R

, K  N (or b = Ax

+ e when there is

measurement noise) by solving a convex program.

As a companion to these papers, this package includes MATLAB code that implements this

recovery procedure in the seven contexts described below. The code is not meant to be cutting-

edge, rather it is a proof-of-concept showing that these recovery procedures are computationally

tractable, even for large scale problems where the number of data points is in the millions.

The problems fall into two classes: those which can be recast as linear programs (LPs), and

those which can be recast as second-order cone programs (SOCPs). The LPs are solved using

a generic path-following primal-dual method. The SOCPs are solved with a generic log-barrier

algorithm. The implementations follow Chapter 11 of [2].

For maximum computational eﬃciency, the solvers for each of the seven problems are imple-

mented separately. They all have the same basic structure, however, with the computational

bottleneck being the calculation of the Newton step (this is discussed in detail below). The code

can be used in either “small scale” mode, where the system is constructed explicitly and solved

exactly, or in “large scale” mode, where an iterative matrix-free algorithm such as conjugate

gradients (CG) is used to approximately solve the system.

Our seven problems of interest are:

• Min-`

with equality constraints. The program

) min kxk

subject to Ax = b,

also known as basis pursuit, ﬁnds the vector with smallest `

norm

kxk

that explains the observations b. As the results in [4, 6] show, if a suﬃciently sparse x

exists such that Ax

= b, then (P

) will ﬁnd it. When x, A, b have real-valued entries, (P

)

can be recast as an LP (this is discussed in detail in [10]).

• Minimum `

error approximation. Let A be a M × N matrix with full rank. Given

y ∈ R

, the program

) min

ky − Axk

ﬁnds the vector x ∈ R

such that the error y − Ax has minimum `

norm (i.e. we are

asking that the diﬀerence between Ax and y be sparse). This program arises in the context

of channel coding [8].

Suppose we have a channel code that produces a codeword c = Ax for a message x. The

message travels over the channel, and has an unknown number of its entries corrupted.

The decoder observes y = c + e, where e is the corruption. If e is sparse enough, then the

decoder can use (P

) to recover x exactly. Again, (P

) can be recast as an LP.

• Min-`

with quadratic constraints. This program ﬁnds the vector with minimum `

norm that comes close to explaining the observations:

) min kxk

subject to kAx − bk

≤ ,

where  is a user speciﬁed parameter. As shown in [5], if a suﬃciently sparse x

exists such

that b = Ax

+ e, for some small error term kek

≤ , then the solution x

to (P

) will be

close to x

. That is, kx

− x

≤ C · , where C is a small constant. (P

) can be recast

as a SOCP.

• Min-`

with bounded residual correlation. Also referred to as the Dantzig Selector,

the program

) min kxk

subject to kA

∗

(Ax − b)k

∞

≤ γ,

where γ is a user speciﬁed parameter, relaxes the equality constraints of (P

) in a diﬀerent

way. (P

) requires that the residual Ax − b of a candidate vector x not be too correlated

with any of the columns of A (the product A

∗

(Ax−b) measures each of these correlations).

If b = Ax

+e, where e

∼ N (0, σ

), then the solution x

to (P

) has near-optimal minimax

risk:

Ekx

− x

≤ C(log N) ·

min(x

(i)

, σ

(see [7] for details). For real-valued x, A, b, (P

) can again be recast as an LP; in the

complex case, there is an equivalent SOCP.

It is also true that when x, A, b are complex, the programs (P

), (P

) can be written as

SOCPs, but we will not pursue this here.

If the underlying signal is a 2D image, an alternate recovery model is that the gradient is

sparse [18]. Let x

denote the pixel in the ith row and j column of an n × n image x, and deﬁne

the operators

h;ij

x =

(

i+1,j

− x

i < n

0 i = n

v;ij

x =

(

i,j+1

− x

j < n

0 j = n

and

x =



h;ij

v;ij



. (1)

The 2-vector D

x can be interpreted as a kind of discrete gradient of the digital image x. The

total variation of x is simply the sum of the magnitudes of this discrete gradient at every point:

TV(x) :=

h;ij

+ (D

v;ij

With these deﬁnitions, we have three programs for image recovery, each of which can be recast

as a SOCP:

• Min-TV with equality constraints.

(T V

) min TV(x) subject to Ax = b

If there exists a piecewise constant x

with suﬃciently few edges (i.e. D

is nonzero for

only a small number of indices ij), then (T V

) will recover x

exactly — see [4].

• Min-TV with quadratic constraints.

(T V

) min TV(x) subject to kAx − bk

≤ 

Examples of recovering images from noisy observations using (T V

) were presented in [5].

Note that if A is the identity matrix, (TV

) reduces to the standard Rudin-Osher-Fatemi

image restoration problem [18]. See also [9, 11–13] for SOCP solvers speciﬁcally designed

for the total-variational functional.

• Dantzig TV.

(T V

) min TV(x) subject to kA

∗

(Ax − b)k

∞

≤ γ

This program was used in one of the numerical experiments in [7].

In the next section, we describe how to solve linear and second-order cone programs using modern

interior point methods.

2 Interior point methods

Advances in interior point methods for convex optimization over the past 15 years, led by the

seminal work [14], have made large-scale solvers for the seven problems above feasible. Below we

overview the generic LP and SOCP solvers used in the `

-magic package to solve these problems.

2.1 A primal-dual algorithm for linear programming

In Chapter 11 of [2], Boyd and Vandenberghe outline a relatively simple primal-dual algorithm

for linear programming which we have followed very closely for the implementation of (P

),(P

and (P

). For the sake of completeness, and to set up the notation, we brieﬂy review their

algorithm here.

The standard-form linear program is

min

, zi subject to A

z = b,

(z) ≤ 0,

where the search vector z ∈ R

, b ∈ R

, A

is a K × N matrix, and each of the f

, i = 1, . . . , m

is a linear functional:

(z) = hc

, zi + d

for some c

∈ R

, d

∈ R. At the optimal point z

, there will exist dual vectors ν

∈ R

, λ

∈

, λ

≥ 0 such that the Karush-Kuhn-Tucker conditions are satisﬁed:

(KKT) c

+ A

= 0,

) = 0, i = 1, . . . , m,

= b,

) ≤ 0, i = 1, . . . , m.

In a nutshell, the primal dual algorithm ﬁnds the optimal z

(along with optimal dual vectors

and λ

) by solving this system of nonlinear equations. The solution procedure is the classical

Newton method: at an interior point (z

, ν

, λ

) (by which we mean f

) < 0, λ

> 0), the

system is linearized and solved. However, the step to new point (z

k+1

, ν

k+1

, λ

k+1

) must be

modiﬁed so that we remain in the interior.

In practice, we relax the complementary slackness condition λ

= 0 to

) = −1/τ

, (2)

where we judiciously increase the parameter τ

as we progress through the Newton iterations.

This biases the solution of the linearized equations towards the interior, allowing a smooth, well-

deﬁned “central path” from an interior point to the solution on the boundary (see [15,20] for an

extended discussion).

The primal, dual, and central residuals quantify how close a point (z, ν, λ) is to satisfying (KKT )

with (2) in place of the slackness condition:

dual

= c

+ A

ν +

cent

= −Λf − (1/τ)1

pri

= A

z − b,

where Λ is a diagonal matrix with (Λ)

= λ

, and f =



(z) . . . f

(z)



From a point (z, ν, λ), we want to ﬁnd a step (∆z, ∆ν, ∆λ) such that

(z + ∆z, ν + ∆ν, λ + ∆λ) = 0. (3)

Linearizing (3) with the Taylor expansion around (z, ν, λ),

(z + ∆z, ν + ∆ν, λ + ∆λ) ≈ r

(z, ν, λ) + J

(z, νλ)





∆z

∆ν

∆λ





where J

(z, νλ) is the Jacobian of r

, we have the system





0 A

−ΛC 0 −F

0 0









∆z

∆v

∆λ





= −





+ A

ν +

−Λf − (1/τ)1

z − b





where m × N matrix C has the c

as rows, and F is diagonal with (F )

= f

(z). We can

eliminate ∆λ using:

∆λ = −ΛF

−1

C∆z − λ − (1/τ)f

−1

(4)

leaving us with the core system



−C

−1

ΛC A



∆z

∆ν





−c

+ (1/τ)C

−1

− A

b − A



. (5)

With the (∆z, ∆ν, ∆λ) we have a step direction. To choose the step length 0 < s ≤ 1, we ask

that it satisfy two criteria:

1. z + s∆z and λ + s∆λ are in the interior, i.e. f

(z + s∆z) < 0, λ

> 0 for all i.

2. The norm of the residuals has decreased suﬃciently:

(z + s∆z, ν + s∆ν, λ + s∆λ)k

≤ (1 − αs) · kr

(z, ν, λ)k

where α is a user-spreciﬁed parameter (in all of our implementations, we have set α = 0.01).

Since the f

are linear functionals, item 1 is easily addressed. We choose the maximum step size

that just keeps us in the interior. Let

= {i : hc

, ∆zi > 0}, I

−

{i : ∆λ < 0},

and set

max

= 0.99 · min{1, {−f

(z)/hc

, ∆zi, i ∈ I

}, {−λ

/∆λ

, i ∈ I

−

}}.

Then starting with s = s

max

, we check if item 2 above is satisﬁed; if not, we set s

= β · s and

try again. We have taken β = 1/2 in all of our implementations.

When r

dual

and r

pri

are small, the surrogate duality gap η = −f

λ is an approximation to how

close a certain (z, ν, λ) is to being opitmal (i.e. hc

, zi − hc

, z

i ≈ η). The primal-dual algorithm

repeats the Newton iterations described above until η has decreased below a given tolerance.

Almost all of the computational burden falls on solving (5). When the matrix −C

−1

ΛC is

easily invertible (as it is for (P

)), or there are no equality constraints (as in (P

), (P

)), (5)

can be reduced to a symmetric positive deﬁnite set of equations.

When N and K are large, forming the matrix and then solving the linear system of equations

in (5) is infeasible. However, if fast algorithms exist for applying C, C

and A

, A

, we can use

a “matrix free” solver such as Conjugate Gradients. CG is iterative, requiring a few hundred

applications of the constraint matrices (roughly speaking) to get an accurate solution. A CG

solver (based on the very nice exposition in [19]) is included with the `

-magic package.

The implementations of (P

), (P

) are nearly identical, save for the calculation of the

Newton step. In the Appendix, we derive the Newton step for each of these problems using

notation mirroring that used in the actual MATLAB code.

2.2 A log-barrier algorithm for SOCPs

Although primal-dual techniques exist for solving second-order cone programs (see [1, 13]), their

implementation is not quite as straightforward as in the LP case. Instead, we have implemented

each of the SOCP recovery problems using a log-barrier method. The log-barrier method, for

which we will again closely follow the generic (but eﬀective) algorithm described in [2, Chap.

11], is conceptually more straightforward than the primal-dual method described above, but at

its core is again solving for a series of Newton steps.

Each of (P

), (T V

) can be written in the form

min

, zi subject to A

z = b

(z) ≤ 0, i = 1, . . . , m (6)

where each f

describes either a constraint which is linear

= hc

, zi + d

or second-order conic

(z) =



− (hc

, zi + d

)



(the A

are matrices, the c

are vectors, and the d

are scalars).

The standard log-barrier method transforms (6) into a series of linearly constrained programs:

min

, zi +

− log(−f

(z)) subject to A

z = b, (7)

评论收藏

内容反馈

Zhsh57

2014-07-03

不好意思，没运行起来。内容蛮全的，给个好评吧。
数据科学家修炼之道

2015-05-30

最近一直在看压缩感知，感觉这个还不错
surprising73

2014-02-08

还行吧，注释太少了
shcnxjy

2022-09-09

谢谢分享，注释再多些就更好了
花开花落@9787

2016-04-11

注释太少了

前往

页

zhyoulun

粉丝: 254
资源: 8

压缩感知Matlab-代码与文档-l1magic-1.11

压缩感知(Compressed Sensing, CS)matlab代码。

压缩感知(Compressed Sensing, CS)matlab代码 实现多个正弦信号的随机欠采样，通过压缩感知恢复

compresssense.rar_MATLAB压缩感知_压缩感知 matlab

压缩感知（内含MATLAB代码）

压缩感知MATLAB程序

TomoSAR.rar_SAR干涉_tomosar matlab_干涉 仿真_干涉SAR 仿真_干涉sar

压缩感知图像matlab代码-compressed_sensing:使用压缩感测的图像压缩

l1-magic工具箱代码

l1magic.rar_L1-magic算法_l1范数最小化_sparse recovery_稀疏恢复_稀疏约束

l1-Magic工具箱

合成孔径雷达（SAR）压缩感知（CS）二维成像Matlab代码。

压缩感知信道估计算法（Matlab 代码）

正交采样Matlab代码-compressed_sensing_bachelor:我的压缩感知学士论文代码（德语）

离散控制Matlab代码-Gaussian-BP-und-Compressed-Sensing:高斯BP和压缩感知

压缩感知算法的MATLAB代码

压缩感知算法的matlab仿真源码

压缩感知(Compressed Sensing, CS)matlab代码

MATLAB：压缩感知（内含完整代码）

压缩感知代码，matlab，romp

l1magic2019.zip

压缩感知图像MATLAB代码（美国乔治亚理工大学）

stanford大学的matlab压缩感知工具箱sparseLab说明文档

压缩感知算法（MATLAB编写，简单易懂，有注释）

压缩感知 图像处理 MATLAB

L1 Magic.zip

L1 Magic实现算法

L1 Magic程序 使用说明 使用示例 相关论文

SAR成像仿真程序

Matlab 基于BP神经网络的数据分类预测 BP分类

Matlab 基于支持向量机(SVM)的数据回归预测 SVM回归

最新资源

压缩感知(Compressed Sensing, CS)matlab代码实现多个正弦信号的随机欠采样，通过压缩感知恢复

TomoSAR.rar_SAR干涉_tomosar matlab_干涉仿真_干涉SAR 仿真_干涉sar

压缩感知图像处理 MATLAB

L1 Magic程序使用说明使用示例相关论文