Open Collections

Theory and algorithms for compressive data acquisition under practical constraints

University of British Columbia

Signal reconstruction from linear measurements is a well-established problem in applied and computational mathematics, data science, and signal processing. In a nutshell, a signal lives in a vector space, and one aims to reconstruct the signal from its linear measurements. This thesis investigates the following real-world scenarios under this setup. Scenario 1. Consider the over-sampled setting and assume that signals to be recovered are known to be sparse. In this case, randomized Kaczmarz and sparse randomized Kaczmarz algorithms are two well-known algorithms that can handle large data. This thesis investigates the reconstruction of sparse signals and the support detection for both algorithms and provides rigorous results for this setting. Scenario 2. As in scenario 1, suppose that signals of interest are known to be sparse and belong to ℝ^N, where N is large, but this time we are in the under-sampled setting. The thesis proposes a novel algorithm called Iterative Reweighted Kaczmarz (IRWK) for recovery of N-dimensional s-sparse signals from their linear measurements in the under-determined setting. The IRWK algorithm uses a single measurement per iteration and requires working memory to be Ο(N). Scenario 3. Suppose that linear measurements of a signal are quantized using Memoryless Scalar Quantization (MSQ), which essentially rounds off each entry to the nearest point in δℤ. The measurements perturbed by the MSQ lead to an inaccurate reconstruction of the signal even in an over-sampled setting (frame quantization). In practice, when the number of measurements m increases, the reconstruction error is observed to decay at a rate of Ο(m⁻¹/²). However, the earlier theory guarantees only Ο(1) error. This thesis bridges theory with the observed results by rigorously proving that the error is in the form of c₁+c₂O(m⁻¹/²) where c₁ and c₂ are independent of m. We prove that c₁ is extremely small for the case of Gaussian measurements and provide sharp bounds on its value. Also, we mathematically justify why we expect c₁ to be small but non-zero for a broad class of random matrices. We also extend the result to the under-determined setting (compressed sensing quantization).

Text

2021-02-10

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/77273

Mathematics

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-nd/4.0/