Quantum Sparse Coding

A ubiquitous problem in machine learning, statistics, and signal processing is to accurately estimate an unknown sparse vector from a few noisy linear measurements. This estimation problem, which we refer to as sparse coding, is at the heart of the field of compressed sensing, revealing that under sparsity assumptions it is possible to successfully recover a signal that sampled significantly below the Nyquist rate [1, 2]. This, in turn, led to a dramatic increase in magnetic resonance imaging (MRI) scanning session speed [3]. Another exciting application that also builds on the sparsity assumption is unsupervised representation learning, i.e., given high-dimensional input data, such as an image, finding a low-dimensional representation that captures the intrinsic underlying structure in the input [4, 5, 6]. These representations are often used in image restoration tasks to effectively remove noise (denoising) [7, 8], fill-in missing pixels (inpainting) [9, 10, 11], and to achieve high quality digital zoom (super-resolution) [10, 12, 13, 14]. Sparsity also plays a key role in linear regression when given a large pool of features, to form a predictive rule that estimates an unknown response using a smaller, interpretable subset of features that manifests the strongest effects [15, 16, 17, 18]. To formalize the sparse coding problem, which is central for tackling the aforementioned applications, we consider the following linear model: b = Ax + v, where A is a matrix of size M N, the vector x is of length N, and v is a noise vector of length M. In this paper, we focus on a challenging setting in which M N, where a crucial assumption we make is that the vector x is k-sparse, i.e., it contains only k non-zero elements with k N [2, 1, 19].