# Covering point-sets with parallel hyperplanes and sparse signal recovery (Lenny Fukshansky, CMC)

- This event has passed.

## Covering point-sets with parallel hyperplanes and sparse signal recovery (Lenny Fukshansky, CMC)

### February 4 @ 12:15 pm - 1:10 pm

Let S be a set of k > n points in n-dimensional Euclidean space. How many parallel hyperplanes are needed to cover it? In fact, it is easy to prove that every such set can be covered by k-n+1 parallel hyperplanes, but do there exist sets that cannot be covered by fewer parallel hyperplanes? We construct a family of examples of such extremal sets. We then use it, along with a result on girth of bipartite graphs, to construct a family of n x d integer matrices with bounded sup-norm and the property that no m column vectors are linearly dependent, m < n. If m < (log n)^{1-e} for any e > 0, then d/n tends to infinity as n tends to infinity. This is a deterministic construction of a family of sensing matrices, which are used for sparse signal recovery in compressed sensing. Joint work with Alex Hsu.