Abstract

Let AA be a matrix whose columns X1,…,XNX_1,\dots, X_N are independent random vectors in Rn\mathbb{R}^n. Assume that the tails of the 1-dimensional marginals decay as P(∣⟨Xi,a⟩∣≥t)≤t−p\mathbb{P}(|\langle X_i, a\rangle|\geq t)\leq t^{-p} uniformly in a∈Sn−1a\in S^{n-1} and i≤Ni\leq N. Then for p>4p>4 we prove that with high probability A/nA/{\sqrt{n}} has the Restricted Isometry Property (RIP) provided that Euclidean norms ∣Xi∣|X_i| are concentrated around n\sqrt{n}. We also show that the covariance matrix is well approximated by the empirical covariance matrix and establish corresponding quantitative estimates on the rate of convergence in terms of the ratio n/Nn/N. Moreover, we obtain sharp bounds for both problems when the decay is of the type exp⁡(−tα) \exp({-t^α}) with α∈(0,2]α\in (0,2], extending the known case α∈[1,2]α\in[1, 2].

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.