Compressed Sensing and the Quadratic Bottleneck Problem: A Combinatorics Approach

Abstract

Compressed sensing is the study of solving underdetermined systems of linear equations with unique sparse solutions. In addition to this, applications of compressed sensing require that the number of rows of the measurement matrix is minimized. In general, the entries of a measurement matrix can be complex. A combinatorial measurement matrix narrows this down to just zeros and ones. These measurement matrices may be obtained from other objects such as the incidence matrix of a combinatorial design or the bipartite adjacency matrix of a bipartite graph. In many applications, a measurement matrix is normally a randomly constructed matrix. This is because it has been shown that with high probability, certain classes of random measurement matrices have on the order of the optimal number of rows required for sparse reconstruction. Finding deterministically constructed classes of measurement matrices whose number of rows scale on the same order as classes of random measurement matrices has been an open problem for at least a decade. This problem is referred to as the quadratic bottleneck problem.