Back to search

University of British Columbia

Compressed sensing with deterministic measurement matrices

Abstract

dc:description

Compressed sensing (CS) is a signal acquisition paradigm to simultaneously acquire and reduce dimension of signals that admit sparse representations. This is achieved by collecting linear, non-adaptive measurements of a signal, which can be formalized as multiplying the signal with a “measurement matrix". If the measurement matrix satisfies the so-called restricted isometry property (RIP), then it will be appropriate for compressed sensing. While wide classes of random matrices provably satisfy the RIP with high probability, explicit and deterministic constructions have been shown (so far) to satisfy the RIP only in a significantly suboptimal regime. In this thesis, our focus is on deterministic measurement matrices in compressed sensing. In a nutshell, we investigate quantization methods for a class of deterministic matrices (Chapter 2); introduce a novel deterministic construction of a family of binary, circulant measurement matrices using the Legendre symbol (Chapter 3); and propose two novel approaches for improving the RIP constant estimates based on Gershgorin circle theorem, obtaining an improvement over the Gershgorin bounds by a multiplicative constant. One of our approaches here, together with a conjecture we make regarding the distribution of quadratic residues in a finite field provides a potential path to break the so-called “square-root barrier"–we give a proof based on the assumption that the conjecture holds.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy - PhD
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Mathematics
Grantor dc:publisher
University of British Columbia
Year dc:date
2019

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Arian, Arman

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/71789

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Arian, Arman. Compressed sensing with deterministic measurement matrices. doctoral thesis, University of British Columbia, 2019. http://hdl.handle.net/2429/71789