Nonuniform compressed sensing schemes with sublinear measurements, sublinear time, and low entropy

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2021-08-05
Authors/Contributors
Author: Lau, Ivan
Abstract
Let x be an unknown vector of length N which has at most k relatively large entries, so that x is well-approximated by its best k-term approximation xk. A compressed sensing scheme consists of a measurement matrix M ∈ C m×N and a recovery algorithm ∆ that approximates xk as xb = ∆ (M,Mx). The scheme is considered accurate if, regardless of the unknown vector x, the approximation xb satisfies kx − xbkp ≤ Ck1/p−1/qkx − xkkq with high probability for some absolute constants C and p ≥ q ≥ 1. Other desirable properties are few measurements (m = O(k polylog N)), fast recovery algorithm (O(k polylog N) runtime), and low entropy. In 2014, Iwen presented two compressed sensing schemes: the fastest known accurate scheme, and the only known fast accurate scheme requiring sublinear entropy. We present a compressed sensing scheme that combines the speed of Iwen's first scheme with the low entropy of Iwen's second scheme, drawing on ideas from disjunct matrix construction due to Porat-Rothschild and Kautz-Singleton. We also give two variants of our scheme. The first variant is deterministic, and has a faster recovery algorithm than all other deterministic accurate schemes. The second variant is measurement-optimal, and requires lower entropy than all other measurement-optimal accurate schemes
Document
Extent
74 pages.
Identifier
etd21544
Copyright statement
Copyright is held by the author(s).
Permissions
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Supervisor or Senior Supervisor
Thesis advisor: Jedwab, Jonathan
Language
English
Member of collection
Attachment Size
etd21544.pdf 1.52 MB