Sparse dictionary learning from 1-BIT data

This work examines a sparse dictionary learning task - that of fitting a collection of data points, arranged as columns of a matrix, to a union of low-dimensional linear subspaces - in settings where only highly quantized (single bit) observations of the data matrix entries are available. We analyze a complexity penalized maximum likelihood estimation strategy, and obtain finite-sample bounds for the average per-element squared approximation error of the estimate produced by our approach. Our results are reminiscent of traditional parametric estimation tasks - we show here that despite the highly-quantized observations, the normalized per-element estimation error is bounded by the ratio between the number of 'degrees of freedom' of the matrix and its dimension.