Derandomized compressed sensing with nonuniform guarantees for _1 recovery

Abstract: We extend the techniques of H"{u}gel, Rauhut and Strohmer (Found. Comput. Math., 2014) to show that for every

d e l t a i n (0, 1]

, there exists an explicit random

m i m e s N

partial Fourier matrix

A

with

m = s o p e r a t o r n a m e p o l y l o g (N / e p s i l o n)

and entropy

s^{d} e l t a o p e r a t o r n a m e p o l y l o g (N / e p s i l o n)

such that for every

s

-sparse signal

x i n m a t h b b C^{N}

, there exists an event of probability at least

1 - e p s i l o n

over which

x

is the unique minimizer of

| z |_{1}

subject to

A z = A x

. The bulk of our analysis uses tools from decoupling to estimate the extreme singular values of the submatrix of

A

whose columns correspond to the support of

x

.

Recommendations

Cites work

Cited in

(8)

Describes a project that uses

Uses Software

This page was built for publication: Derandomized compressed sensing with nonuniform guarantees for \(\ell_1\) recovery