F-最小化在稀疏恢复中的鲁棒性：拓扑视角

76 浏览量更新于2024-07-15 收藏 547KB PDF 举报

"这篇研究论文探讨了F-最小化在稀疏恢复中的鲁棒性，并从拓扑视角进行了分析。" 在信息技术领域，压缩感知（Compressed Sensing）是一门重要的理论，它允许从少量的测量数据中恢复高维信号。近年来，非凸优化技术在稀疏恢复中的应用成为了一个热门趋势，其中F-最小化（F-minimization）尤为引人关注。F-最小化是一种非线性的优化方法，特别适用于寻找稀疏解，即那些大部分元素为零的解。论文中指出，在无噪声环境下，F-最小化的确切恢复条件（Exact Reconstruction Condition，ERC）可以通过测量矩阵的零空间属性（Null Space Property，NSP）精确地刻画。NSP是衡量测量矩阵能否确保稀疏信号恢复的关键属性。然而，当存在噪声时，关于F-最小化的鲁棒恢复条件（Robust Reconstruction Condition，RRC）的研究相对较少。作者们将测量矩阵的零空间视为 Grassmann 曼ifold 上的一个点，进而研究ERC集合（记为 J）与RRC集合（记为 r J）之间的关系。他们证明了RRC集合实际上是ERC集合的内部（即 r J = int(J)），这意味着在无噪声情况下，ERC与RRC等价的结果可以作为特殊情况轻松得出。这是一个重要的发现，因为它提供了在有噪声环境下F-最小化仍能有效恢复稀疏信号的理论基础。此外，当F是单调不减的函数时，论文进一步表明ERC集合的边界（即 J \ int(J)）具有测度为零且属于第一类别（First Category）的特性。这一结论意味着在大多数情况下，ERC和RRC的概率是接近的，从而增强了F-最小化在实际应用中的鲁棒性。这篇论文深入研究了F-最小化在稀疏恢复中的稳健性，从拓扑角度给出了新的理解，并提供了噪声环境中恢复条件的理论框架。这对于理解和改进压缩感知算法，特别是在实际信号处理和数据恢复场景中，有着重要的指导意义。

LIU et al.: ROBUSTNESS OF SPARSE RECOVERY VIA F-MINIMIZATION 3999

so that the key optimization problems in many of the sparse

recovery algorithms can be subsumed in our framework,

including 

-minimization and ZAP algorithm. The deﬁnition

is also quite natural, since it can be checked that F is

a sparseness measure if and only if its corresponding cost

function J induces a metric on R

via d(x, y) := J(x − y).

When F ∈ M,thenull space property (NSP) turns out to

be equivalent with ERC:

Lemma 1 (Null Space Property [8] (Lemma 6)): If F∈M,

then a necessary and sufﬁcient condition for ERC is

J(z

)<J (z

), ∀z ∈ N (A) \{0}, T :|T |≤k. (11)

where N (A) denotes the null space of A.

It’s useful to deﬁne the null space constant [8], especially

when one wants to study 

-minimization or to compare it

with F-minimization:

Deﬁnition 4 (Null Space Constant, NSC): Suppose F ∈M,

q ∈ (0, 1]. Deﬁne the null space constant is deﬁned as:

:= sup

z∈N (A)\{0}

max

|T |≤k

J(z

)

J(z

)

. (12)

In the same spirit, we denote by θ



the null space constant

associated with 

cost function.

The null space constant is closely associated with NSP,

and hence characterizes the performance of F-minimization.

We have the following result, which is a direct consequence

of Deﬁnition 4 and Lemma 1.

Lemma 2:

1) θ

≤ 1 is a necessary condition for ERC;

2) θ

< 1 is a sufﬁcient condition for ERC.

In the case of 

-minimization, one can obtain the following

characterization (see [19]), which is more exact than the case

of F-minimization as described in Lemma 2:

Lemma 3: For 

cost functions, θ



< 1 is a both neces-

sary and sufﬁcient condition for ERC.

C. Preliminaries of the Grassmann Manifold

In this subsection we brieﬂy review some relevant properties

of the Grassmann manifold. More detailed treatment of this

subject and related concepts in differential topology can be

found in many standard texts, such as [23] and [24]. The

main thrust for considering this object is that, by Lemma 1 the

property of exact recovery of a particular measurement matrix

is completely determined by its null space N (A), which is an

l := n − m dimensional linear subspace of R

when A is of

full rank.

Geometrically, the Grassmann manifold G

) can be

conceived as the collection of all the l dimensional subspaces

(l-planes) of R

. One can introduce a topology on G

)

by deﬁning a metric on it: for arbitrary ν, ν



∈ G

),the

distance between ν, ν



can be deﬁned as [25]:

dist(ν, ν



) := P

− P



, (13)

where P

(resp. P



) is the projection matrix onto ν (resp. ν



and ·denotes the spectral norm. The Grassmann manifold

is then a compact metric space.

We shall next deﬁne the coordinates on G

) to introduce

its differential manifold structure. Let F(n, l) be the set of

all non-degenerate (invertible) n × l matrices, and let ∼ be

the following equivalence relation: If X, Y ∈ F(n, l),then

X ∼ Y if there is an l × l invertible matrix V such that

Y = XV. Hence the Grassmann manifold can be deﬁned as a

quotient space G

) := F(n, l)/∼, for which we denote by

π : F(n, l) → G

) the associated natural projection. For

any arbitrary collection of indices 1 ≤ i

< i

< ···< i

≤ n,

let 1 ≤

< ··· <

n−l

≤ n be the remaining indices.

GivenanindexsetI ={i

, i

,...,i

}, we denote by X

the

l ×l sub-matrix formed by the rows of X indexed by I .Deﬁne

:= {X ∈ F(n, l) | det X

= 0}, (14)

:= π(U

). (15)

Then {U

} constitutes an open covering of G

).For

Y ∈ π

−1

(ν),whereν ∈ U

, the matrix X = YY

−1

an invariant of ν, meaning that for any other

Y ∈ π

−1

(ν),

)

−1

= X.SinceX

is the l × l identity matrix, X is

determined by X

.Deﬁneφ

: U

→ M(n −l, l), v → X

We call each (U

,φ

) a chart.Then{(U

,φ

) | 1 ≤

< ···< i

≤ n} forms an atlas of G

), meaning that U

covers G

) and any two charts in this collection

are C

∞

compatible.

Concepts such as open sets and interior are well-deﬁned

once a topology on G

) has been unambiguously chosen.

One might notice that there are possibly two topologies deﬁned

on G

): the metric topology arising from the metric deﬁned

in (13), and the manifold topology (which is connected to the

standard topology on R

by all the homeomorphisms {φ

}).

Unsurprisingly these two topologies agree, since standard

calculations would show that the metric on U

induced from

the Euclidean metric on φ

) is topologically equivalent to

the metric deﬁned in (13).

Further, since G

) is a C

∞

(therefore differentiable)

manifold, the concept of measure zero set can be deﬁned as

follows:

Deﬁnition 5 [24, Deﬁnition 1.16]: A subset A of a differ-

entiable manifold has measure zero if φ(A ∩U) has Lebesgue

measure zero for every chart (U,φ).

Remark 1: The differentiability of the manifold ensures that

the deﬁnition of the measure zero set is “consistent” for the

various choices of φ. In particular, to check that a set A

is of measure zero, one only needs to pick a collection of

homeomorphisms {φ

}

I∈S

whose domains cover U, and check

that φ

(A ∩U

) has measure zero for each I ∈ S.

The Haar measure, denoted as μ, is the unique probability

measure on G

) which is invariant with respect to the

orthogonal group’s action on G

), that is, the action on

the quotient space G

) induced from the action of left

multiplication of n × n orthogonal matrix on F(n, l).The

requirement that a set A has zero Haar measure agrees with

Deﬁnition 5 [23]. The Haar measure is of practical importance,

since it coincides with the probability distribution of the null

space of A when A is rotationally invariant,thatis,the

distribution of A is the same as that of AQ for any orthogonal

matrix Q. In particular, this is true when A is a (standard)

Gaussian random matrix.

剩余18页未读，继续阅读

weixin_38697471

粉丝: 6
资源: 981

F-最小化在稀疏恢复中的鲁棒性：拓扑视角

Python库 | robustness-1.0.post1-py3-none-any.whl

In Defense of Color-based Model-free Tracking

java test plan for matrix

Influence of Autoencoder-Based Data Augmentation on Deep Learning-Based Wireless Communication

orbslam2+imu

How can we evaluate the robustness of a machine learning system可以给我一个解释吗

multi-scale

配置adversarial-robustness-toolbox==1.7.2 torch==1.7.1 torchvision==0.8.2 numpy argparse tqdm pandas dill cox tables tensorboardX的步骤

signless Laplacian

最新资源