FromSparseSolutionsofSystems...资源-CSDN文库

5星 · 超过95%的资源需积分: 41 150 浏览量 2012-04-17 10:39:28 上传评论 1 收藏 2.06MB PDF 举报

### 关于系统方程稀疏解到信号与图像稀疏建模的研究 #### 概述本文探讨了从系统方程的稀疏解到信号与图像稀疏建模的理论和应用进展。研究始于线性代数的一个基本问题：如何找到一个欠定线性方程组 \(Ax = b\)（其中 \(A \in \mathbb{R}^{n \times m}\) 且 \(n < m\)）中最稀疏的解，即非零元素最少的解。这种类型的解在许多实际应用场景中具有重要意义，尤其是在信号处理和图像处理领域。 #### 稀疏解的基本概念在考虑一个欠定线性方程组时，存在无穷多个解。然而，在某些情况下，我们可能对寻找最稀疏的解感兴趣。这里的“稀疏”是指解向量中非零元素的数量尽可能少。这样的解在信号处理、压缩感知等领域中尤为重要。 #### 理论背景 1. **唯一性**：尽管欠定系统有无限多解，但特定条件下，最稀疏的解可能是唯一的。 2. **计算方法**：虽然优化稀疏性本质上是组合问题，但在过去几年中已经发展出有效的算法来找到最稀疏的解，如基础追踪（Basis Pursuit）和匹配追踪（Matching Pursuit）等方法。 #### 条件与结果为了找到最优稀疏解，必须满足一定的条件，这些条件通常涉及矩阵 \(A\) 的特性。例如，矩阵的列之间不能过于相关，这通常通过互相干(coherence)的概念来衡量。如果矩阵满足某些条件，则可以证明稀疏解的存在性和可恢复性，并且可以通过有效算法求得。 #### 应用领域 - **信号处理**：稀疏表示在压缩感知、去噪等方面发挥着重要作用。例如，利用稀疏表示可以实现高效的数据压缩，同时保持信号的质量。 - **图像处理**：在图像恢复、去模糊、超分辨率等问题中，稀疏模型同样具有显著的优势。通过对图像进行稀疏表示，可以在一定程度上恢复丢失或模糊的信息。 #### 具体实例 - **逆问题**：在逆问题中，稀疏模型能够帮助解决由噪声数据引起的不稳定问题。通过寻找稀疏解，可以有效地抑制噪声的影响，提高重建质量。 - **压缩**：在图像压缩方面，利用稀疏表示可以实现更高的压缩比，同时保持良好的视觉效果。这对于存储和传输大量图像数据尤其重要。 #### 结论本文深入讨论了从系统方程的稀疏解到信号与图像稀疏建模的相关理论和技术。通过理论分析和实验验证，表明了在满足一定条件下，欠定系统的最稀疏解是存在的，并且可以通过有效算法找到。这些成果不仅丰富了数学理论，而且为信号和图像处理领域的实际应用提供了强有力的支持。未来的研究将继续探索更高效的算法以及更广泛的应用场景，推动这一领域的持续发展。

资源推荐

资源详情

资源评论

SIAM REVIEW



2009 Society for Industrial and Applied Mathematics

Vol. 51, No. 1, pp. 34–81

From Sparse Solutions of

Systems of Equations to Sparse

Modeling of Signals and Images

∗

Alfred M. Bruckstein

†

David L. Donoho

‡

Michael Elad

Abstract. A full-rank matrix A ∈ R

n×m

with n<mgenerates an underdetermined system of linear

equations Ax = b having inﬁnitely many solutions. Suppose we seek the sparsest solution,

i.e., the one with the fewest nonzero entries. Can it ever be unique? If so, when? As opti-

mization of sparsity is combinatorial in nature, are there eﬃcient methods for ﬁnding the

sparsest solution? These questions have been answered positively and constructively in

recent years, exposing a wide variety of surprising phenomena, in particular the existence

of easily veriﬁable conditions under which optimally sparse solutions can be found by con-

crete, eﬀective computational methods. Such theoretical results inspire a bold perspective

on some important practical problems in signal and image processing. Several well-known

signal and image processing problems can be cast as demanding solutions of undetermined

systems of equations. Such problems have previously seemed, to many, intractable, but

there is considerable evidence that these problems often have sparse solutions. Hence, ad-

vances in ﬁnding sparse solutions to underdetermined systems have energized research on

such signal and image processing problems—to striking eﬀect. In this paper we review the

theoretical results on sparse solutions of linear systems, empirical results on sparse mod-

eling of signals and images, and recent applications in inverse problems and compression

in image processing. This work lies at the intersection of signal processing and applied

mathematics, and arose initially from the wavelets and harmonic analysis research commu-

nities. The aim of this paper is to introduce a few key notions and applications connected

to sparsity, targeting newcomers interested in either the mathematical aspects of this area

or its applications.

Key words. underdetermined, linear system of equations, redundant, overcomplete, sparse represen-

tation, sparse coding, basis pursuit, matching pursuit, mutual coherence, Sparse-Land,

dictionary learning, inverse problems, denoising, compression

AMS subject classiﬁcations. 68U10, 94A08, 15A29, 15A06, 90C25

DOI. 10.1137/060657704

1. Introduction. A central achievement of classical linear algebra was a thorough

examination of the problem of solving systems of linear equations. The results—

∗

Received by the editors April 20, 2006; accepted for publication (in revised form) July 23, 2007;

published electronically February 5, 2009. This work was supported in part by the Israel Science

Foundation (ISF) grant 796/05, by the Binational Science Foundation (BSF) grant 2004199, and by

an Applied Materials research fund.

http://www.siam.org/journals/sirev/51-1/65770.html

†

Computer Science Department, The Technion–Israel Institute of Technology, Haifa, 32000 Israel

(freddy@cs.technion.ac.il).

‡

Statistics Department, Stanford University, Stanford, CA 94305 (donoho@stat.stanford.edu).

Corresponding author: Computer Science Department, The Technion–Israel Institute of Tech-

nology, Haifa, 32000 Israel (elad@cs.technion.ac.il).

SPARSE MODELING OF SIGNALS AND IMAGES 35

deﬁnite, timeless, and profound—give the subject a completely settled appearance.

Surprisingly, within this well-understood arena there is an elementary problem which

only recently has been explored in depth; we will see that this problem has surprising

answers and inspires numerous practical developments.

1.1. Sparse Solutions of Linear Systems of Equations?. Consider a full-rank

matrix A ∈ R

n×m

with n<m, and deﬁne the underdetermined linear system of

equations Ax = b. This system has inﬁnitely many solutions; if one desires to

narrow the choice to one well-deﬁned solution, additional criteria are needed. Here

is a familiar way to do this. Introduce a function J(x) to evaluate the desirability

of a would-be solution x, with smaller values being preferred. Deﬁne the general

optimization problem (P

) : min

J(x) subject to b = Ax.(1)

Selecting a strictly convex function J(·) guarantees a unique solution. Most readers

are familiar with this approach from the case where J(x) is the squared Euclidean

norm x

. The problem (P

) (say), which results from that choice, has in fact a

unique solution

x—the so-called minimum-norm solution; this is given explicitly by

= A

b = A

(AA

)

−1

The squared 

norm is of course a measure of energy; in this paper, we consider

instead measures of sparsity. A very simple and intuitive measure of sparsity of a

vector x simply involves the number of nonzero entries in x; the vector is sparse

if there are few nonzeros among the possible entries in x. It will be convenient to

introduce the 

“norm”

x

=#{i : x

=0}.

Thus if x

 m, x is sparse.

Consider the problem (P

) obtained from the general prescription (P

) with the

choice J(x)=J

(x) ≡x

; explicitly,

) : min

x

subject to b = Ax.(2)

Sparsity optimization (2) looks superﬁcially like the minimum 

-norm problem

), but the notational similarity masks some startling diﬀerences. The solution

to (P

) is always unique and is readily available through now-standard tools from

computational linear algebra. (P

) has probably been considered to be a possible

goal from time to time for many years, but initially it seems to pose many conceptual

challenges that have inhibited its widespread study and application. These are rooted

in the discrete and discontinuous nature of the 

norm; the standard convex analysis

ideas which underpin the analysis of (P

) do not apply. Many of the most basic

questions about (P

) seem immune to immediate insight:

• Can uniqueness of a solution be claimed? Under what conditions?

• If a candidate solution is available, can we perform a simple test to verify

that the solution is actually the global minimizer of (P

Perhaps, in some instances, with very special matrices A and left-hand sides b, ways

to answer such questions are apparent, but for general classes of problem instances

(A, b), such insights initially seem unlikely.

36 ALFRED M. BRUCKSTEIN, DAVID L. DONOHO, AND MICHAEL ELAD

Beyond conceptual issues of uniqueness and veriﬁcation of solutions, one is easily

overwhelmed by the apparent diﬃculty of solving (P

). This is a classical problem

of combinatorial search; one sweeps exhaustively through all possible sparse subsets,

generating corresponding subsystems b = A

, where A

denotes the matrix with

|S| columns chosen from those columns of A with indices in S, and checking whether

b = A

can be solved. The complexity of exhaustive search is exponential in

m and, indeed, it has been proven that (P

) is, in general, NP-hard [125]. Thus, a

mandatory and crucial set of questions arises: Can (P

) be eﬃciently solved by some

other means? Can approximate solutions be accepted? How accurate can those be?

What kind of approximations will work?

In fact, why should anyone believe that any progress of any kind is possible here?

Here is a hint. Let x

denote the 

norm



|, and consider the problem (P

)

obtained by setting J(x)=J

(x)=x

. This problem is somehow intermediate

between (P

) and (P

). It is a convex optimization problem, and among convex

problems it is in some sense the one closest to (P

). We will see below [49, 93, 46]

that for matrices A with incoherent columns, whenever (P

) has a suﬃciently sparse

solution, that solution is unique and is equal to the solution of (P

). Since (P

)is

convex, the solution can thus be obtained by standard optimization tools—in fact,

linear programming. Even more surprisingly, for the same class A, some very simple

greedy algorithms (GAs) can also ﬁnd the sparsest solution to (P

) [156].

Today many pure and applied mathematicians are pursuing results concerning

sparse solutions to underdetermined systems of linear equations. The results achieved

so far range from identifying conditions under which (P

) has a unique solution, to

conditions under which (P

) has the same solution as (P

), to conditions under which

the solution can be found by some “pursuit” algorithm. Extensions range even more

widely, from less restrictive notions of sparsity to the impact of noise, the behavior of

approximate solutions, and the properties of problem instances deﬁned by ensembles

of random matrices. We hope to introduce the reader to some of this work below and

provide some appropriate pointers to the growing literature.

1.2. The Signal Processing Perspective. We now know that ﬁnding sparse so-

lutions to underdetermined linear systems is a better-behaved and much more prac-

tically relevant notion than we might have supposed just a few years ago.

In parallel with this development, another insight has been developing in signal

and image processing, where it has been found that many media types (still imagery,

video, acoustic) can be sparsely represented using transform-domain methods, and in

fact many important tasks dealing with such media can be fruitfully viewed as ﬁnding

sparse solutions to underdetermined systems of linear equations.

Many readers will be familiar with the media encoding standard JPEG and its

successor, JPEG-2000 [153]. Both standards are based on the notion of transform

encoding. The data vector representing the raw pixel samples are transformed—

i.e., represented in a new coordinate system—and the resulting coordinates are then

processed to produce the encoded bitstream. JPEG relies on the discrete cosine

transform (DCT)—a variant of the Fourier transform—while JPEG-2000 relies on the

discrete wavelet transform (DWT) [116]. These transforms can be viewed analytically

as rotations of coordinate axes from the standard Euclidean basis to a new basis. Why

does it make sense to change coordinates in this way? Sparsity provides the answer.

The DCT of media content often has the property that the ﬁrst several transform

coeﬃcients are quite large and later ones are very small. Treating the later coeﬃcients

as zeros and approximating the early ones by quantized representations yields an

SPARSE MODELING OF SIGNALS AND IMAGES 37

approximate coeﬃcient sequence that can be eﬃciently stored in a few bits. The

approximate coeﬃcient sequence can be inverse transformed to yield an approximate

representation of the original media content. The DWT of media content has a slightly

diﬀerent property: there are often a relatively few large coeﬃcients (although they

are not necessarily the “ﬁrst” ones). Approximating the DWT by setting to zero

the small coeﬃcients and quantizing the large ones yields a sequence to be eﬃciently

stored and later inverse transformed to provide an approximate representation of the

original media content. The success of the DWT in image coding is thus directly

tied to its ability to sparsify image content. For many types of image content, JPEG-

2000 outperforms JPEG: fewer bits are needed for a given accuracy or approximation.

One underlying reason is that the DWT of such media is more sparse than the DCT

representation.

In short, sparsity of representation is key to widely used techniques of transform-

based image compression. Transform sparsity is also a driving factor for other impor-

tant signal and image processing problems, including image denoising [50, 51, 27, 43,

53, 52, 144, 124, 96] and image deblurring [76, 75, 74, 41]. Repeatedly, it has been

shown that a better representation technique—one that leads to more sparsity—can

be the basis for a practically better solution to such problems. For example, it has

been found that for certain media types (e.g., musical signals with strong harmonic

content), sinusoids are best for compression, noise removal, and deblurring, while for

other media types (e.g., images with strong edges), wavelets are a better choice than

sinusoids.

Realistic media may be a superposition of several such types, conceptually re-

quiring both sinusoids and wavelets. Following this idea leads to the notion of joining

together sinusoids and wavelets in a combined representation. Mathematically this

now lands us in a situation similar to that described in the previous section. The basis

of sinusoids alone makes an n × n matrix, and the basis of wavelets makes an n × n

matrix; the concatenation makes an n ×2n matrix. The problem of ﬁnding a sparse

representation of a signal vector b using such a system is exactly the same as that of

the previous section. We have a system of n equations in m =2n unknowns, which

we know is underdetermined; we look to sparsity as a principle to ﬁnd the desired

solution.

We can make this connection formal as follows. Let b denote the vector of sig-

nal/image values to be represented, and let A be the matrix whose columns are the

elements of the diﬀerent bases to be used in the representation. The problem (P

)

oﬀers literally the sparsest representation of the signal content.

1.3. Measuring Sparsity. The 

norm, while providing a very simple and easily

grasped notion of sparsity, is not the only notion of sparsity available to us, nor is

it really the right notion for empirical work. A vector of real data would rarely be

representable by a vector of coeﬃcients containing many strict zeros. A weaker notion

of sparsity can be built on the notion of approximately representing a vector using a

small number of nonzeros; this can be quantiﬁed by the weak 

norms, which mea-

sure the tradeoﬀ between the number of nonzeros and the 

error of reconstruction.

Denoting by N(, x) the number of entries in x exceeding , these measures of sparsity

are deﬁned by

x

w

= sup

>0

N(, x) · 

A second important reason for the superiority of JPEG-2000 is its improved bit-plane-based

quantization strategy.

38 ALFRED M. BRUCKSTEIN, DAVID L. DONOHO, AND MICHAEL ELAD

Here 0 <p≤ 1 is the interesting range of p, giving a very powerful sparsity constraint.

The weak 

norm is a popular measure of sparsity in the mathematical analysis

community; models of cartoon images have sparse representations as measured in

weak 

[26, 13].

Almost equivalent are the usual 

norms, deﬁned by

x







1/p

These will seem more familiar objects than the weak 

norms, in the range 1 ≤ p ≤∞;

however, for measuring sparsity, 0 <p<1 is of most interest.

It would seem very natural, based on our discussion of media sparsity, to attempt

to solve a problem of the form

) : min x

subject to Ax = b,(3)

for example, with p =1/2orp =2/3. Unfortunately, each choice 0 <p<1 leads to

a nonconvex optimization problem which is very diﬃcult to solve in general.

At this point, our discussion of the 

norm in section 1.1 can be brought to bear.

The 

norm is naturally related to the 

norms with 0 <p<1; all are measures of

sparsity and, in fact, the 

norm is the limit as p → 0ofthe

norms in the following

sense:

x

= lim

p→0

x

= lim

p→0



k=1

.(4)

Figure 1 presents the behavior of the scalar weight function |x|

—the core of the norm

computation—for various values of p, showing that as p goes to zero, this measure

becomes a count of the nonzeros in x.

−2 −1.

−1 −

5 0 0

1 1.

0.5

1.5

p=0.1

p=1

p=0.5

p=2

Fig. 1 The behavior of |x|

for various values of p.Asp tends to zero, |x|

approaches the indicator

function, which is 0 for x =0and 1 elsewhere.

Note that among the 

norms, the choice p = 1 gives a convex functional, while

every choice 0 <p<1 yields a concave functional. We have already mentioned

that solving (P

) can sometimes be attacked by solving (P

) instead, or by using an

appropriate heuristic GA; the same lesson applies here: although we might want to

solve (P

) we should do better by instead solving (P

) or by applying an appropriate

heuristic GA.

1.4. This Paper. The keywords “sparse,” “sparsity,” “sparse representations,”

“sparse approximations,” and “sparse decompositions” are increasingly popular; the

剩余47页未读，继续阅读

评论收藏

内容反馈

zhyj8810

2013-05-24

正在学习这方面的东西很不错好厚
静夜星光

2013-05-17

这篇文章写得不错！
mingyi

2014-06-08

很有深度的文章
现在就跑

2015-11-05

很好，文章写的还行
shashaschumi

2013-05-05

对我来说有难度啊

前往

页

scucj

粉丝: 424
资源: 6

From Sparse Solutions of Systems...

最新资源

From Sparse Solutions of Systems...

From Sparse Solutions of Systems of Equations to Sparse Modeling

Direct Methods for Sparse Matrices (I. S. Duff, A. M. Erisman, J. K. Reid)

PyPI 官网下载 | torch_sparse-0.6.12.tar.gz

torch_sparse-0.6.17+pt113cpu-cp39-cp39-linux_x86_64.whl.zip

Iterative Methods for Sparse Linear Systems

torch_sparse-0.6.17-cp37-cp37m-macosx_10_15_x86_64.whl.zip

Matlab interface for sparse nonlinear optimizer SNOPT.zip

torch_sparse-0.6.15-cp38-cp38-macosx_10_15_x86_64.whl.zip

torch_sparse-0.6.17-cp310-cp310-macosx_10_15_x86_64whl.zip

torch_sparse-0.6.17+pt113cpu-cp310-cp310-win_amd64.whl.zip

42使用CROWDSOURCED SPARSE MAP_new.pdf

Iterative methods for sparse linear systems (1st edition)

torch_sparse-0.6.16+pt113cpu-cp39-cp39-win_amd64.whl.zip

torch_sparse-0.6.17+pt113cpu-cp37-cp37m-win_amd64.whl.zip

OpenMVS ：用 colmap制作自己的数据集 文件下载 sparse,scene.mvs

sparse principal component analysis.pdf

torch_sparse-0.6.17+pt113cpu-cp310-cp310-linux_x86_64.whl.zip

Python库 | tf_sparse-0.0.1.tar.gz

Direct_Methods_for_Sparse_Linear_Systems

Python库 | torch_sparse-0.2.0.tar.gz

Iterative Methods for sparse linear space.pdf

torch_sparse-0.6.17+pt113cu117-cp37-cp37m-win_amd64.whl

torch_sparse-0.6.15-cp39-cp39-macosx_10_15_x86_64.whl.zip

仿真电路以及操作方法

python大作业 含爬虫、数据可视化、地图、报告、及源码（整和为一个文件）（2014-2020全国各地区原油加工量）.rar

【纯干货啊】华为IPD流程管理(完整版).pptx

信号与系统——保研复习资料.pdf

最新资源

OpenMVS ：用 colmap制作自己的数据集文件下载 sparse,scene.mvs

python大作业含爬虫、数据可视化、地图、报告、及源码（整和为一个文件）（2014-2020全国各地区原油加工量）.rar