Seminars & Colloquia Calendar

Download as iCal file

DIMACS Theory of Computing Seminar

An Improved Lower Bound for Sparse Reconstruction from Subsampled Hadamard Matrices

Jaroslaw Blasiok (Columbia)

Location:  CoRE 301
Date & time: Wednesday, 30 October 2019 at 11:00AM - 12:00PM

Abstract: We give a short argument that yields a new lower bound on the number of subsampled rows from a bounded, orthonormal matrix necessary to form a matrix with the restricted isometry property. We show that a matrix formed by uniformly subsampling rows of an N×N Hadamard matrix contains a K-sparse vector in the kernel, unless the number of subsampled rows is ?(KlogKlog(N/K)) --- our lower bound applies whenever min(K,N/K)>logCN. Containing a sparse vector in the kernel precludes not only the restricted isometry property, but more generally the application of those matrices for uniform sparse recovery.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.