高精度随机投影下稀疏信号近似恢复策略

需积分: 32 109 浏览量更新于2024-07-28 收藏 458KB PDF 举报

"《近似最优信号恢复：随机投影的通用编码策略》是一篇发表在2006年IEEE Transactions on Information Theory第52卷第12期的研究论文。该论文探讨了一个核心问题：如何仅通过少量线性测量就能有效地从数据集中恢复出信号，特别是针对稀疏或压缩的数字信号和图像。作者Emmanuel J. Candès和Terence Tao提出了一个革命性的理论，表明如果信号在固定基底下的非零分量遵循特定的衰减规律，即第n个分量不大于n的p次方分之一（其中R>0且0<p<1），即使面对大量的数据，只需通过独立的标准正态分布的随机投影矩阵（N维高斯向量）进行测量，也能实现接近最优的信号恢复。具体来说，论文的核心贡献是提出了一种算法，通过最小化1范数（L1正则化）来解决线性方程组yk = hf(Xki)，其中yk是关于信号f的测量，Xk是随机投影矩阵。这个方法被称作“压缩 sensing”（Compressive Sensing），它展示了即使在数据维度远大于所需恢复信息的情况下，仍能以高效的方式重构信号。当满足信号的稀疏性或压缩性条件时，解出的重构信号f']与原始信号f之间的误差非常小，具有很高的准确度，而且这种结果在统计上具有很高的概率。这篇论文的重要性在于它揭示了随机投影在信号处理中的强大潜力，特别是在现代大数据和机器学习背景下，它提供了一种理论基础和实用工具，使得我们在处理大规模、高维数据时能够有效地进行信息提取和恢复。通过解决这个理论问题，Candès和Tao的工作不仅推动了信号处理领域的进步，还对后续的低秩矩阵恢复、图像处理、通信系统和分布式计算等领域产生了深远影响。"

CANDES AND TAO: NEAR-OPTIMAL SIGNAL RECOVERY FROM RANDOM PROJECTIONS 5409

As we will see later, Theorem 1.1 is a special case of The-

orem 1.2 below (but for the uniqueness claim which is proved

in Section III).

D. Precedents

A natural question is whether the number of random sam-

ples we identiﬁed in Theorem 1.2 is, in some sense, optimal. Or

would it be possible to obtain similar accuracies with far fewer

observations? To make things concrete, suppose we are inter-

ested in the recovery of objects with bounded

-norm, e.g., the

-ball

Suppose we can make linear measurements about

of the form . Then what is the best measurement/

reconstruction pair so that the error

(1.12)

is minimum? In (1.12),

is the reconstruction algorithm. To

develop an insight about the intrinsic difﬁculty of our problem,

consider the following geometric picture. Suppose we take

measurements ; this says that belongs to an afﬁne space

where is a linear subspace of co-dimension less or

equal to

.Nowthe data available for the problem cannot dis-

tinguish any object belonging to that plane. Assume

is known

to belong to the

-ball , say, then the data cannot distinguish

between any two points in the intersection

. There-

fore, any reconstruction procedure

based upon

would obey

(1.13)

(When we take the supremum over all

, we may just assume

that

is orthogonal to the measurements since the

diameter will of course be maximal in that case.) The goal is

then to ﬁnd

such that the above diameter is minimal. This

connects with the agenda of approximation theory where this

problem is known as ﬁnding the Gelfand

-width of the class

[12], as we explain below.

The Gelfand numbers of a set

are deﬁned as

(1.14)

where

is, of course, the orthonormal projection on the sub-

space

. Then it turns out that .

Now a seminal result of Kashin [13] and improved by Garnaev

and Gluskin [14], [15] shows that for the

ball, the Gelfand

numbers obey

(1.15)

where

are universal constants. Gelfand numbers are also

approximately known for weak-

balls as well.

Viewed differently, Kashin, Garnaev and Gluskin assert

that with

measurements, the minimal reconstruction error

(1.12) one can hope for is bounded below by a constant times

. In this sense, Theorem 1.2 is optimal

(within a multiplicative constant) at least for

, with

Kashin also shows that if we take a random projection,

is bounded above by the right-hand side of

(1.15). We would also like to emphasize that similar types of

recovery have also been known to be possible in the literature

of theoretical computer science, at least in principle, for certain

types of random measurements [17]. On the one hand, ﬁnding

the Chebyshev center of

is a convex problem,

which would yield a near-optimal reconstruction algorithm.

On the other hand, this problem is computationally intractable

when

. Further, one would need to know and the

radius of the weak-

ball which is not realistic in practical

applications.

The novelty here is that the information about

can be re-

trieved from those random coefﬁcients by minimizing a simple

linear program (1.10), and that the decoding algorithm adapts

automatically to the weak-

signal class, without knowledge

thereof. Minimizing the

-norm gives nearly the best possible

reconstruction error simultaneously over a wide range of sparse

classes of signals; no information about

and the radius are

required. In addition and as we will see next, another novelty is

the general nature of the measurement ensemble.

It should also be mentioned that when the measurement en-

semble consists of Fourier coefﬁcients on a random arithmetic

progression, a very fast recovery algorithm that gives near-op-

timal results for arbitrary

data has recently been given in [18].

Since the preparation of this manuscript, we have learnt that re-

sults closely related to those in this paper have appeared in [19].

We compare our results with both these works in Section IX.B.

E. Other Measurement Ensembles

Underlying our results is a powerful machinery essentially

relying on properties of random matrices which gives us very

precise tools allowing us to quantify how much of a signal one

can reconstruct from random measurements. In fact, Theorem

1.1 holds for other measurement ensembles. For simplicity, we

shall consider three types of measured data.

• The Gaussian ensemble: Here, we suppose that

and are ﬁxed, and the entries of

are identically and independently sampled from a standard

normal distribution

i.i.d.

The Gaussian ensemble is invariant by rotation since for

any ﬁxed orthonormal matrix

, the distribution of is

that of

• The binary ensemble: Again we take

and

to be ﬁxed. But now we suppose that the

entries of

are identically and independently sampled

from a symmetric Bernoulli distribution

i.i.d.

Note Added in Proof: Since submission of this paper, we proved in [16] that

Theorem 1.2 holds with

log(

N=K

)

instead of

log

in (1.11).

剩余19页未读，继续阅读

paradiseyidian

粉丝: 0
资源: 2

高精度随机投影下稀疏信号近似恢复策略

Optimal BPM：打造下一代开源业务流程管理系统

SEO优化利器：Optimal title插件使用指南

"选择放大器以及其与ADC的接口优化：放大器和位数（TI）

Collaborated Tasks-driven Mobile Charging and Scheduling: A Near Optimal Result

Patch-based Near-Optimal Image Denoising

Near-optimal One-sided Scheduling for Coded Segmented Network Coding

ARM: Distributed Near-Optimal Discrete Power Control in Wireless Networks

Optimal binary codes from one-lee weight codes and two-lee weight projective codes over Z_4

Near-Optimal and Practical Jamming-Resistant Energy-Efficient Cognitive Radio Communications

PMPSO:A Near-Optimal Graph Planarization Algorithm using Probability Model basedParticle Swarm Optimization

最新资源