On unique recovery of integer bounded signals

Alasmari, Abdullah 2023. On unique recovery of integer bounded signals. PhD Thesis, Cardiff University. Item availability restricted.

Preview	PDF - Accepted Post-Print Version Download (1MB) | Preview
	PDF (Cardiff University Electronic Publication Form) - Supplemental Material Restricted to Repository staff only Download (749kB)

Abstract

The thesis considers the problem of unique recovery of finite-valued integer signals using a single linear integer measurement. A signal is an integer ndimensional vector x with absolute entries bounded by a positive integer r, that is x ∈ [−r, r]n. We assume that the signal x is sufficiently sparse. Specifically, the number of nonzero entries of x is assumed to be bounded by a positive integer l with 2l < n. A single linear integer measurement is represented by an integer 1 × n measurement matrix, or row vector, H. Naturally, it is desirable to construct H with as small absolute entries as possible. We give a constructive proof for the existence of measurement matrices H with maximum absolute entry Δ = O(r2l−1). The capital O in this bound contains an implicit constant that depends on l and n and probably far from being optimal, however the exponent 2l −1 is optimal. The optimality of the exponent is the main advantage of the latter upper bound. Additionally, we show that, in the above setting, a single measurement can be replaced by several measurements with absolute entries sub-linear in Δ. The proofs make use of results on admissible (n − 1)-dimensional integer lattices for m-sparse ncubes that are of independent interest. The main tools include the aggregation of linear Diophantine equations and Siegel’s lemma. Additionally, we discuss some probabilistic aspects of unique recovery for finite-valued integer signals.

Item Type:	Thesis (PhD)
Date Type:	Completion
Status:	Unpublished
Schools:	Mathematics
Date of First Compliant Deposit:	7 December 2023
Last Modified:	07 Dec 2023 16:00
URI:	https://orca.cardiff.ac.uk/id/eprint/164597

Actions (repository staff only)

Edit Item