[2205.06738] Sparsity and $\ell_p$-Restricted Isometry

2 years ago

source link: https://arxiv.org/abs/2205.06738
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

[Submitted on 13 May 2022]

Sparsity and ℓp-Restricted Isometry

Download PDF

A matrix A is said to have the ℓp-Restricted Isometry Property (ℓp-RIP) if for all vectors x of up to some sparsity k, ∥Ax∥p is roughly proportional to ∥x∥p. It is known that with high probability, random dense m×n matrices (e.g., with i.i.d.\ ±1 entries) are ℓ2-RIP with k≈m/logn, and sparse random matrices are ℓp-RIP for p∈[1,2) when k,m=Θ(n). However, when m=Θ(n), sparse random matrices are known to \emph{not} be ℓ2-RIP with high probability.
With this backdrop, we show that there are no sparse matrices with ±1 entries that are ℓ2-RIP. On the other hand, for p≠2, we show that any ℓp-RIP matrix \emph{must} be sparse. Thus, sparsity is incompatible with ℓ2-RIP, but necessary for ℓp-RIP for p≠2.

Subjects:	Computational Complexity (cs.CC); Information Theory (cs.IT)
Cite as:	arXiv:2205.06738 [cs.CC]
	(or arXiv:2205.06738v1 [cs.CC] for this version)
	https://doi.org/10.48550/arXiv.2205.06738

Recommend

arxiv.org 4 years ago
Cache

[1902.02134] Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsi...

[Submitted on 6 Feb 2019 (v1), last revised 27 Nov 2019 (this version, v4)] Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factori...

hackernoon.com 3 years ago
Cache

Out of Options: The Sparsity of Hedging Solutions in the Crypto Space

Out of Options: The Sparsity of Hedging Solutions in the Crypto SpaceMay 20th 2021 new story7

www.nextplatform.com 3 years ago
Cache

Reimagining Accelerators with Sparsity at the Core

Reimagining Accelerators with Sparsity at the Core There could be a new era of codesign dawning for machine learning, one that moves away from the training and inference separations and toward far less dense networks with highly spa...