压缩感知经典文章（附程序）_压缩感知论文资源-CSDN文库

共16个文件

m：10个

mat：5个

pdf：1个

matlab

压缩感知

5星 · 超过95%的资源需积分: 50 140 浏览量 2014-05-09 22:26:15 上传评论 5 收藏 1.52MB ZIP 举报

资源推荐

资源详情

资源评论

收起资源包目录

Blind Multiband Signal Reconstruction_Compressed Sensing for Analog Signals.zip （16个子文件）

PolyFilterDecimate.m 785B

Results_4Shift5.mat 169KB

FindNonZeroValues.m 591B

SimEngine.m 15KB

GenFigs.m 3KB

CollapseResults.mat 143KB

is_contained.m 171B

Results_10Shift5.mat 142KB

eig_r.m 308B

MixSignal.m 394B

Results_20Shift5.mat 130KB

start.m 951B

Results_100Shift1.mat 127KB

RunOMP_forMB.m 3KB

Blind Multiband Signal Reconstruction_Compressed Sensing for Analog Signals.pdf 1020KB

FilterDecimate.m 478B

IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 57, NO. 3, MARCH 2009 993

Blind Multiband Signal Reconstruction: Compressed

Sensing for Analog Signals

Moshe Mishali, Student Member, IEEE, and Yonina C. Eldar, Senior Member, IEEE

Abstract—We address the problem of reconstructing a multi-

band signal from its sub-Nyquist pointwise samples, when the

band locations are unknown. Our approach assumes an existing

multi-coset sampling. To date, recovery methods for this sampling

strategy ensure perfect reconstruction either when the band

locations are known, or under strict restrictions on the possible

spectral supports. In this paper, only the number of bands and

their widths are assumed without any other limitations on the sup-

port. We describe how to choose the parameters of the multi-coset

sampling so that a unique multiband signal matches the given

samples. To recover the signal, the continuous reconstruction

is replaced by a single ﬁnite-dimensional problem without the

need for discretization. The resulting problem is studied within

the framework of compressed sensing, and thus can be solved

efﬁciently using known tractable algorithms from this emerging

area. We also develop a theoretical lower bound on the average

sampling rate required for blind signal reconstruction, which is

twice the minimal rate of known-spectrum recovery. Our method

ensures perfect reconstruction for a wide class of signals sampled

at the minimal rate, and provides a ﬁrst systematic study of com-

pressed sensing in a truly analog setting. Numerical experiments

are presented demonstrating blind sampling and reconstruction

with minimal sampling rate.

Index Terms—Landau–Nyquist rate, multiband, multiple mea-

surement vectors (MMV), nonuniform periodic sampling, sparsity.

I. INTRODUCTION

HE well-known Whittaker, Koteln

ikov, and Shannon

(WKS) theorem links analog signals with discrete repre-

sentations, allowing signal processing in a digital framework.

The theorem states that a real-valued signal bandlimited to

Hertz can be perfectly reconstructed from its uniform samples if

the sampling rate is at least

samples per second. This state-

ment highlights the basic ingredients of a sampling theorem.

First, a signal model which appears in practical applications

and relates to physical properties. In this case, the maximal fre-

quency

parameterizes a bandlimited signal model. Second,

a minimal rate requirement to allow perfect reconstruction,

referred to as the Nyquist rate in the WKS setting. Finally, a

design of sampling and reconstruction stages which is based on

the model parameters.

Manuscript received September 11, 2007; revised November 24, 2008. First

published January 13, 2009; current version published February 13, 2009.

The associate editor coordinating the review of this manuscript was Dr. Zoran

Cvetkovic.

The authors are with the Technion—Israel Institute of Technology, Haifa

32000, Israel (e-mail: moshiko@tx.technion.ac.il; yonina@ee.technion.ac.il).

Color versions of one or more of the ﬁgures in this paper are available online

at http://ieeexplore.ieee.org.

Digital Object Identiﬁer 10.1109/TSP.2009.2012791

In this paper, we consider the class of multiband signals,

whose frequency support resides within several continuous

intervals, spread over a wide spectrum. This model naturally

arises when observing the sum of a few narrowband trans-

missions which are modulated by relatively high carriers,

with different frequencies. When the band locations and their

widths are known prior to sampling, the signal model deﬁnes a

subspace of possible inputs. Landau [1] developed a minimal

rate requirement for an arbitrary sampling method that allows

perfect reconstruction in this setting. The Landau rate equals

the sum of the band widths, which is below the corresponding

Nyquist rate. Several works proposed sampling and reconstruc-

tion stages, designed according to the speciﬁc spectral support

of the input signal. Low-rate uniform sampling was studied in

[2] for a real bandpass signal, whereas [3] suggested periodic

nonuniform sampling at the same average sampling rate. Lin

and Vaidyanathan [4] extended this approach to multiband sig-

nals. These methods allow exact recovery at rates approaching

that derived by Landau.

A much more challenging problem is to design a

blind sam-

pling and reconstruction system, that does not rely on knowl-

edge of the band locations. Blindness is important whenever

detecting the spectral support, prior to sampling, is impossible

or too expensive to implement. Reconstruction under partial

knowledge of the support was addressed in a series of confer-

ence papers [5]–[7]. These works do not assume the exact sup-

port but require that the band locations obey a certain math-

ematical condition. Sampling is carried out by a multi-coset

strategy, independent of the band locations. In order to recover

the signal, [5], [6] identiﬁed similarities with direction of ar-

rival problems, implying potential use of techniques from this

ﬁeld, such as MUSIC [8]. An alternative method was proposed

in [7] under the assumption that the support obeys a strict math-

ematical condition. Similar results were derived in [9]. This ap-

proach, however, suffers from two main drawbacks. First, as de-

tailed in Section V-B, if the support violates the condition of [7],

then the samples match many possible input signals, thus hin-

dering any chance for recovery. Since this condition depends on

the band locations which are unknown, it cannot be validated in

practice. The difﬁculty arises form the fact that this requirement

is not directly related to simple physical properties of a multi-

band model (i.e., the number of bands and their widths). Second,

even when the condition is met, exact recovery is not guaran-

teed. This is a result of the fact that the proposed sampling rate

approaches that dictated by Landau. As we prove in Section III,

perfect blind reconstruction requires a higher sampling rate.

In subsequent publications, Herley and Wong [10] suggested

a half-blind system. Similar ideas were later suggested in [11].

994 IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 57, NO. 3, MARCH 2009

Fig. 1. Three RF transmissions with different carriers

. The receiver sees a

multiband signal (bottom drawing). In this example the real-valued signal con-

tains

bands, and the modulation techniques of the transmitters determine

the maximal expected width

In this case, the signal is sampled using a multi-coset sampling

strategy, independent of the band locations. However, recovery

is based on knowledge of the spectral support. This approach

guarantees perfect (nonblind) recovery under the same condi-

tion of [7]. Thus, to date, there exist no spectrum-blind method

that is guaranteed to recover a multiband signal (with arbitrary

band positions) at rates lower than the Nyquist rate.

A. Main Contributions

Following the ingredients of the WKS theorem, we begin by

formulating a multiband model

which contains signals with

at most

bands, whose widths do not exceed . Fig. 1 depicts

a typical communication application that obeys the model

Once the signal model is established, we develop a minimal rate

requirement for blind perfect reconstruction of signals from

with an arbitrary system. As we show, the lower bound is twice

the Landau rate and no more than the Nyquist rate.

The body of this paper focuses on spectrum-blind reconstruc-

tion (SBR) assuming a preceding multi-coset stage which sat-

isﬁes the minimal rate requirement. Our ﬁrst main result de-

scribes a parameter selection for the sampling stage such the

every signal in

matches a unique digital representation. This

selection relies on the known values

, but does not impose

any restrictions on the band locations. We show that this choice

is also valid for known-spectrum reconstruction with half the

sampling rate.

Our approach to blind recovery is to ﬁrst determine the spec-

tral support from the given samples. Once the support is recov-

ered, the reconstruction has a closed form solution, which mo-

tivates this paradigm. Theoretical tools are developed in order

to transform the continuous support recovery problem into a ﬁ-

nite-dimensional program without any discretization. We then

prove that the solution can be obtained by ﬁnding the unique

sparsest solution matrix from multiple measurement vectors.

This set of operations is grouped under a block we name Con-

tinuous to Finite (CTF). This block is the cornerstone of two

SBR algorithms we develop. One is entitled SBR4 and uses a

single instance of the CTF. SBR4 guarantees perfect reconstruc-

tion when sampling at twice the minimal rate. The other is re-

ferred to as SBR2 and involves a bi-section process and several

uses of the CTF block. SBR2 works at the minimal rate, but

does not guarantee exact recovery for certain multiband signals.

Other differences between the algorithms are also discussed.

Both SBR4 and SBR2 can easily be implemented in DSP pro-

cessors or in software environments.

The CTF block requires ﬁnding a sparsest solution matrix

which is an NP-hard problem [13]. Several suboptimal efﬁcient

methods have been developed for this problem in the com-

pressed sensing (CS) literature [13], [14]. In our algorithms,

any of these techniques can be used. However, when using a

suboptimal technique in SBR4, exact recovery is no longer

guaranteed. Fortunately, numerical experiments on random

constructions of multiband signals from

show that both

SBR4 and SBR2 maintain a satisfactory exact recovery for min-

imal sampling rate even when suboptimal implementations of

the CTF block are used. In addition, SBR4 is accompanied with

a nice feature which indicates the recovery success, allowing

to switch between suboptimal techniques in case of a failure.

While discussing experimental results, we also address stability

under measurement noise and emphasize the advantages of

SBR4 and SBR2 over a simple inexact discretization-based

reconstruction.

B. Compressed Sensing for Analog Signals

In his seminal work on compressed sensing [15], Donoho

posed the ultimate goal of merging compression and sampling.

In such an approach, the actual information contents dictate

the sampling rate, rather than the dimensions of the ambient

space in which the signal resides. This goal triggered a surge

of research on various mathematical and algorithmic aspects

of sensing sparse signals, which were mainly studied for dis-

crete and ﬁnite vectors. The present work takes a ﬁrst step to-

wards sensing in a truly continuous environment. An adapta-

tion of CS results to continuous signals was also considered in

a series of conferences papers (see [16] and [17] and the refer-

ences therein). However, these papers did not address the case

of multiband signals. In [16], a vector signal was assumed, but

the generalization to continuous signals was not studied, while

in [17] an underlying discrete model was used so that the contin-

uous signal is a linear combination of a ﬁnite number of known

functions. Here, there is no discrete model as the signals are

treated in a continuous framework without any discretization.

A second aspect that distinguishes our work from main-

stream CS papers relates to tractability of the recovery. From

a sampling viewpoint, perfect reconstruction is a desired goal

even when yielding a difﬁcult recovery stage (i.e., an NP-hard

problem). The WKS theorem, for example, suggests an ideal

lowpass ﬁlter for reconstruction, whose practical implementa-

tion is highly demanding. The approach in compressive sensing

promotes the opposite viewpoint and strives for tractable

recovery algorithms at the expense of suboptimality in the

sampling rate [13]–[15], [24].

C. Outline

The paper is organized as follows. In Section II, we formu-

late the signal model and the reconstruction goals. The minimal

rate theorem for blind reconstruction is stated and proved in

Section III. A brief overview of multi-coset sampling is pre-

sented in Section IV. We develop our main theoretical results

on spectrum-blind reconstruction and present the CTF block in

Since submission of the report [18] and the conference version [19], we

have further expanded the analog CS framework in several follow-up papers;

see [20]–[23].

MISHALI AND ELDAR: BLIND MULTIBAND SIGNAL RECONSTRUCTION 995

TABLE I

OTATION

Section V. Based on these results, in Section VI, we design and

compare the SBR4 and SBR2 algorithms. Numerical experi-

ments are described in Section VII.

II. S

IGNAL MODEL AND PROBLEM FORMULATION

A. Multiband Signal Model

Common notation, as summarized in Table I, is used

throughout the paper. It is assumed that

is a continuous

function of

, and that the Fourier transform

(1)

is (piecewise) continuous in

The following multiband model is the prime focus of our

work.

Deﬁnition 1: The set

contains all complex-valued signals

satisfying the following:

is bandlimited to , namely

;

is further restricted to have a support on no more than

disjoint intervals (bands) in ; and

3) the band widths do not exceed

Fig. 2 depicts a typical spectral support of a multiband signal

. The Nyquist rate corresponding to any is

. Note that each band is uniquely represented by its edges

; however, the band positions of are arbitrary,

and in particular, unknown in advance.

Fig. 2. Typical spectrum support of

(

)

Although our interest is mainly in signals

, our results

are applicable to a broader class of signals, as explained in the

relevant sections. In addition, the results of the paper are easily

adopted to real-valued signals supported on

The required modiﬁcations are detailed in Appendix A.

B. Problem Formulation

We wish to perfectly reconstruct

from a set of

pointwise samples under two constraints. One is blindness, so

that the information about the band locations is not used while

acquiring the samples and neither can it be used in the recon-

struction process. The other is that the sampling rate required to

guarantee perfect reconstruction should be minimal.

This problem is solved if either of the constraints is removed.

Without the rate constraint, the WKS theorem allows perfect

blind-reconstruction for every signal

bandlimited to

from its uniform samples at the Nyquist rate. Alter-

natively, if the exact number of bands and their locations are

known, then under mild conditions on the band positions the

method of [4] allows perfect reconstruction at the minimal

sampling rate provided by Landau’s theorem [1].

III. M

INIMAL SAMPLING RAT E

We begin by quoting Landau’s theorem for the minimal

sampling rate of an arbitrary sampling method that allows

known-spectrum perfect reconstruction. We then develop a

similar theorem for blind reconstruction, which proves that

twice the Landau rate is required to allow for exact recovery.

A. Known Spectrum Support

Consider the space of bandlimited functions whose Fourier

transform is restricted to a known support

(2)

A set

is called a sampling set for if the sequence

of samples

is stable, namely there exist con-

stants

and such that

(3)

Landau [1] proved that if

is a sampling set for then it must

have a density

, where

(4)

is the lower Beurling density, and

is the Lebesgue measure

. The numerator in (4) counts the number of points from

996 IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 57, NO. 3, MARCH 2009

in every interval of width of the real axis.

The Beurling

density (4) reduces to the usual concept of average sampling

rate for uniform and periodic nonuniform sampling. The Landau

rate,

, is the minimal average sampling rate for .

B. Unknown Spectrum Support

Consider the set of signals bandlimited to with band-

width occupation no more than

, so that

(5)

The Nyquist rate for

is . Note that is not a subspace

so that the Landau theorem does not apply here. Nevertheless,

it is intuitive to argue that the minimal sampling rate for

cannot be below as this value is the Landau rate had the

spectrum support been known.

A blind sampling set

for is a stable sampling set whose

design does not assume knowledge of

. Similarly to

(3) the stability of

requires the existence of and

such that

(6)

Theorem 1 (Minimal Sampling Rate): Let

be a blind sam-

pling set for

. Then

(7)

Proof: The set

is of the form

(8)

where

is deﬁned by (2) and

(9)

Clearly,

is an uncountable union of subspaces. Sampling

signals that lie in a union of subspaces has been recently treated

in [12]. For every

deﬁne the subspaces

(10)

Since

is a sampling set for , (6) holds for some constants

. It was proved in ([12], Proposition 2) that (6) is

valid if and only if

(11)

holds for every

. In particular, is a sampling set for

every

with .

Now, the space

is of the form (2) with .

Applying Landau’s theorem for each

results in

(12)

The numerator is not necessarily ﬁnite but as the sampling set is countable

the inﬁmum takes on a ﬁnite value.

Choosing

(13)

we have that for

(14)

, then and

(15)

Combining (14) and (15) completes the proof.

In [12], the authors consider minimal sampling requirements

for a union of shift-invariant subspaces, with a particular

structure of sampling functions. Speciﬁcally, they view the

samples as inner products with sampling functions of the form

, which includes multi-coset sampling.

Theorem 1 extends this result to an arbitrary pointwise sam-

pling operator. In particular, it is valid for aperiodic sampling

sets that are not covered by [12].

An immediate corollary of Theorem 1 is that if

then

uniform sampling at the Nyquist rate and reconstruction with

an ideal lowpass ﬁlter satisﬁes the requirements of our problem

formulation: sampling and reconstruction are independent of the

band locations, and the sampling rate is minimal. Since

contained in the space of bandlimited signals, this choice pro-

vides perfect reconstruction for every

. Therefore, in

the sequel we assume that

so that the minimal sampling

rate is twice the Landau rate.

It is easy to see that

is a true subset of for .

The Proof of Theorem 1 can be adapted to show that sampling

at an average rate of

is necessary to allow blind perfect

reconstruction for all signals from

(for ).

For known spectral support of

, the Landau rate is

Both Landau’s theorem and Theorem 1 state a lower bound

but do not provide a method to achieve the bound. An important

distinction between the two theorems is that for known spectrum

the set

is linear (namely, closed under linear combinations)

and known reconstruction schemes [4], [11] are also linear. Con-

sequently, the stability condition (3) sufﬁces to ensure stability

of the reconstruction. In contrast,

is a nonlinear set (as is

), and our proposed reconstruction scheme is also nonlinear.

Theorem 1 states the necessary density for a blind stable sam-

pling set while a higher density may be required to ensure stable

reconstruction.

The rest of the paper is devoted to developing a reconstruction

method that approaches the minimal sampling rate of Theorem

1 while ensuring perfect reconstruction. We address stability in

Section VII-C.

IV. U

NIVERSAL SAMPLING

This section reviews multi-coset sampling which is used in

our development. We also brieﬂy explain the fundamentals of

known-spectrum reconstruction as derived in [11].

MISHALI AND ELDAR: BLIND MULTIBAND SIGNAL RECONSTRUCTION 997

A. Multi-Coset Sampling

Uniform sampling of

at the Nyquist rate results in sam-

ples

that contain all the information about . Multi-

coset sampling is a selection of certain samples from this grid.

The uniform grid is divided into blocks of

consecutive sam-

ples. A constant set

of length describes the indexes of

samples that are kept in each block. The set is re-

ferred to as the sampling pattern where

(16)

Deﬁne the

th sampling sequence for as

otherwise

(17)

The sampling stage can be implemented by

uniform sampling

sequences with period

, where the th sampling sequence

is shifted by

from the origin.

Direct calculations link the known discrete-time Fourier

transform

of to the unknown Fourier trans-

form

of :

(18)

for every

, and every in the interval

(19)

It is convenient to express (18) in matrix form as

(20)

where

is a vector of length whose th element is

is a matrix with th element given by

(21)

and the vector

contains unknowns for each

(22)

Fig. 3 illustrates the relation between

and . The

problem of recovering

is equivalent to determining

from for all .

Dealing with real-valued multiband signals requires simple

modiﬁcations to (20). These adjustments are detailed in

Appendix A.

The average sampling rate of a multi-coset sampling set is

(23)

Fig. 3. Vector

(

)

is constructed by slicing

(

)

into

equal-length inter-

vals, and rearranging them in vector form.

which is lower than the Nyquist rate for . However, an

average sampling rate above the Landau rate is not sufﬁcient

for known-spectrum reconstruction. Additional conditions are

needed as explained in the next section.

B. Known-Spectrum Reconstruction and Universality

Presentation of the reconstruction is simpliﬁed using CS spar-

sity notation. A vector

is called -sparse if the number of

nonzero values in

is not greater than . We also

use the following deﬁnition of the Kruskal-rank of a matrix [25]:

Deﬁnition 2: The Kruskal-rank of

, denoted , is the

maximal number

such that every set of columns of is

linearly independent.

Observe that for every

the system (20) has fewer

equations than unknowns. However, when incorporating the

structure of

as prior, the number of unknowns may be

reduced. As evident from Fig. 3, every band can contribute

several nonzero values to

. Thus, in order to match the

number of equations to the number of unknowns, it is necessary

that

-sparse (24)

In [11] it is assumed that the information about the band lo-

cations is available for reconstruction, so that the support set

is known for every . In this setting, a sufﬁcient

condition for a unique solution in (20) can be formulated using

the Kruskal-rank of

-sparse (25)

The known-spectrum reconstruction of [11] basically restricts

the columns of

to and inverts the resulting matrix in

order to recover

A sampling pattern

that yields a fully Kruskal-rank

, is called universal and corresponds to

[11]. Therefore, the set of signals that are consistent with (25)

is the broadest possible if a universal sampling pattern is used.

As we show later, choosing

and a universal

pattern

makes (25) valid for every signal .

评论收藏

内容反馈

Zhsh57

2014-08-04

这个资料超级好，很全面，有程序。
xiazaizhe下载

2014-07-14

是一篇analog cs 的经典论文，程序很详细
delly0816

2014-06-10

和好，是个初学者学习
lanldok

2019-12-05

可以参考下，感谢
gong_li_mei

2015-07-19

非常好用，帮了我大忙了，十分感谢！

sssyyd

粉丝: 0
资源: 1

压缩感知经典文章（附程序）

Compressed sensing 文章

一篇很好的有关压缩感知文章（概述性）

压缩感知文献综述

压缩感知各种重构算法经典论文合集 MP OMP SAMP SP CoSaMP IHT等

压缩感知程序

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

压缩感知MATLAB程序

压缩感知_消失矩的演示

压缩感知_均值插值

关于压缩感知的经典论文

压缩感知好文章

压缩感知的综述文章

压缩感知综述文章

压缩感知方面的程序

压缩感知文献10篇

压缩感知_立方插值

压缩感知CS资源合集_MATALB代码_参考论文_重构算法

【硕士论文代码】matlab图像处理，压缩感知中ROMP的代码实现.rar

分布式压缩感知经典文献

压缩感知的程序

压缩感知插值程序

压缩感知技术的几个小程序

分块压缩感知程序

压缩感知BP算法程序

matlab编写的压缩感知程序

压缩感知程序,压缩感知程序及分析,C,C++

最新资源