Beyond Worst-Case Dimensionality Reduction for Sparse Vectors

We study beyond worst-case dimensionality reduction for s-sparse vectors (vectors with at most s non-zero coordinates). Our work is divided into two parts, each focusing on a different facet of beyond worst-case analysis: (a) We first consider average-case guarantees for embedding s-sparse vectors. Here, a well-known folklore upper bound based on the birthday-paradox states: For any collection X of s-sparse vectors in R d , there exists a linear map A : R d → R O(s 2 ) which exactly preserves the norm of 99% of the vectors in X in any ℓ p norm (as opposed to the usual setting where guarantees hold for all vectors). We provide novel lower bounds showing that this is indeed optimal in many settings. Specifically, any oblivious linear map satisfying similar average-case guarantees must map to Ω(s 2 ) dimensions. The same lower bound also holds for a wider class of sufficiently smooth maps, including 'encoder-decoder schemes', where we compare the norm of the original vector to that of a smooth function of the embedding. These lower bounds reveal a surprising separation result for smooth embeddings of sparse vectors, as an upper bound of O(s log(d)) is possible if we instead use arbitrary functions, e.g., via compressed sensing algorithms.