Donoho Starks uncertainty principles limit approximate supports for k Hadamard operators
On approximate support versions of Donoho--Stark uncertainty principles for $k$-Hadamard operators
Information Theory
Summary
This paper looks at mathematical rules called uncertainty principles, which say you can’t know too much about certain pairs of properties in signals at once. The authors focus on versions that allow some approximation, working with special matrices called k-Hadamard operators. They find these rules hold for some ranges of mathematical measures but fail outside those ranges, clarifying exactly when such approximations are possible. Their results pinpoint limitations and conditions for these uncertainty principles in a finite setting.
What this means in practice
- •For signal processing engineers: Determine when approximate sparsity constraints hold for transforms using k-Hadamard operators to better design signal acquisition and reconstruction.
- •For cryptography system designers: Identify limitations on approximate support in matrix transforms which can aid in analyzing security constraints in cryptographic schemes using special operators.
A theory result. No direct application yet.
Authors
Rami Ayoush
Abstract
In this paper we present results related to Donoho--Stark type uncertainty principles that were proved in the article "The uncertainty principle: variations on a theme" by Wigderson and Wigderson for $k$-Hadamard operators in the finite-dimensional setting. Namely, the authors showed that Donoho-Stark principles can be generalized to versions for approximate supports with respect to norms $\ell^{p}$ for $p=1$ and $p=2$. In the second case they assumed the so-called speciality condition, namely that a suitable matrix satisfies $A^{*}A = kI$. First we show that such theorems cannot be generalized to $p>1$ if matrices are not special $k$-Hadamard. Next we prove Donoho-Stark type principle for special $k$-Hadamard operators for $\ell^{p}$ norms within the range $1\leq p\leq 2$. Finally, we show that such theorems are false for $p>2$ even in the presence of the speciality condition.