Explicit constructions of RIP matrices and related problems

Mathematics – Number Theory

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

v3. Minor corrections

Scientific paper

We give a new explicit construction of $n\times N$ matrices satisfying the Restricted Isometry Property (RIP). Namely, for some c>0, large N and any n satisfying N^{1-c} < n < N, we construct RIP matrices of order k^{1/2+c}. This overcomes the natural barrier k=O(n^{1/2}) for proofs based on small coherence, which are used in all previous explicit constructions of RIP matrices. Key ingredients in our proof are new estimates for sumsets in product sets and for exponential sums with the products of sets possessing special additive structure. We also give a construction of sets of n complex numbers whose k-th moments are uniformly small for 1\le k\le N (Turan's power sum problem), which improves upon known explicit constructions when (\log N)^{1+o(1)} \le n\le (\log N)^{4+o(1)}. This latter construction produces elementary explicit examples of n by N matrices that satisfy RIP and whose columns constitute a new spherical code; for those problems the parameters closely match those of existing constructions in the range (\log N)^{1+o(1)} \le n\le (\log N)^{5/2+o(1)}.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Explicit constructions of RIP matrices and related problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Explicit constructions of RIP matrices and related problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Explicit constructions of RIP matrices and related problems will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-704256

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.