Loading...
Please wait, while we are loading the content...
Similar Documents
Almost euclidean subspaces of ℓ n 1 via expander codes (2009).
| Content Provider | CiteSeerX |
|---|---|
| Author | Guruswami, Venkatesan Lee, James R. Razborov, Alexander A. |
| Abstract | We give an explicit (in particular, deterministic polynomial time) construction of subspaces X ⊆ R N of dimension (1 − o(1))N such that for every x ∈ X, (log N) −O(log log log N) √ N ‖x‖2 � ‖x‖1 � √ N ‖x‖2. If we are allowed to use N 1/log log N � N o(1) random bits and dim(X) � (1 − η)N for any fixed constant η, the lower bound can be further improved to (log N) −O(1) √ N‖x‖2. Through known connections between such Euclidean sections of ℓ1 and compressed sensing matrices, our result also gives explicit compressed sensing matrices for low compression factors for which basis pursuit is guaranteed to recover sparse signals. Our construction makes use of unbalanced bipartite graphs to impose local linear constraints on vectors in the subspace, and our analysis relies on expansion properties of the graph. This is inspired by similar constructions of error-correcting codes. |
| File Format | |
| Publisher Date | 2009-01-01 |
| Access Restriction | Open |
| Subject Keyword | Expander Code Euclidean Subspace Error-correcting Code Log Log Euclidean Section Log Log Log Unbalanced Bipartite Graph Fixed Constant Deterministic Polynomial Time Sparse Signal Local Linear Constraint Expansion Property Basis Pursuit Random Bit Low Compression Factor Similar Construction Analysis Relies |
| Content Type | Text |
