Discrepancy-Based Analysis of Measurement Sampling Points in Compressive Sensing

Compressive sensing (CS) is a technique in signal processing that under certain conditions allows someone to reconstruct sparse signals from fewer linear measurements. A problem in CS is modeled in terms of an underdetermined linear system, whose associated matrix is previously designed. Then, it is of interest in CS to know what a good sampling defined by the sensing matrix is and how to measure it. In this work, we provided analytical proofs of properties of the metric discrepancy that allow us to propose a fast algorithm for discrepancy calculation. Such metric measures the quality of the sampling measurement points in the sensing matrix. Moreover, we show that discrepancy is a predictor of the quality of signal reconstructions in CS problems. In this dissertation, we also develop structured sampling schemes that have low-discrepancy properties, which imply with high probability good signal reconstructions. Finally, we propose an adaptation of the log-barrier algorithm to recover real-valued signals from complex-valued measurements by solving an ℓ1-optimization problem with quadratic constraints. This work is based on qualitative and quantitative methodologies. For instance, the adapted log-barrier and discrepancy algorithms are designed in terms of analytical results or properties that are proved in this work. On the quantitative side, reconstructions of signals in CS problems are performed by solving thousands of Monte Carlo simulations along with discrepancy calculations. The results show that discrepancy can effectively predict the quality of sparse signal reconstructions in noisy CS problems. Moreover, it has advantage over condition number, which is invariant for orthonormal matrices. The simulations show that frequency vectors of the discrete Fourier Transform ( sensing matrix) taken randomly as subsequences of low-discrepancy sequences produce with high probability good signal reconstructions in terms of signal-to-error ratio. Hence, we show this for the class of Kronecker sequences that are designed by means of fractional parts of multiples of irrational numbers modulo 1. An outstanding case of this class is the golden sequence, which has unique and peculiar numerical properties. Finally, another contribution of this dissertation is the analytical discussion and then the development of the proposed adapted log-barrier algorithm that can handle complex-valued measurements to reconstruct sparse signals in ℓ1-optimization problems with quadratic constraint. Furthermore, there was a contribution to the literature by expanding, in detail, the complex calculations of the Newton’s step of the log-barrier algorithm that we extended. Such algorithm is one of the first ones in compressive sensing, and its analytical development is not straightforward. Therefore, a full development of its calculations is a contribution to the literature equivalent to the work of a Master’s thesis. Future work can be done towards refined discrepancy measures and corresponding algorithms to multidimensional signals. Moreover, applications on medical imaging sampling can be designed based on low-discrepancy characteristics. In another direction, CS can be merged with deep learning for applications in MRI