Solving Sparse Representation for Object Classification Using Quantum D-Wave 2X Machine

Abstract: Finding sparse representations of images is an important problem in computer vision, with applications including denoising, upsampling, compression and object detection. Moreover, sparse coding explains many of the response properties of simple cells in the mammalian primary visual cortex [1]. Given an overcomplete basis, sparse coding algorithms seek to identify the minimal set of generators that most accurately reconstruct each input image. In neural terms, each neuron is a generator that adds its associated feature vector to the reconstructed image with an amplitude equal to its activation. For any particular input image, the optimal sparse representation is given by the vector of neural activations that minimizes both image reconstruction error and the number of neurons with non-zero activity. When using binary neurons, analogous to applying an L0 sparseness penalty, sparse coding falls into an NP-hard complexity class of decision problems, i.e. solving this optimization problem is at least as hard as a (NP-complete) problem that can be solved by a nondeterministic-Turing machine in polynomial time. Sparse coding with an L0 norm sparseness penalty poses considerable difficulty due to the fact that the energy function is non-convex and contains multiple local minima [2]. Here, we investigate the application of Quantum Annealing to the solution of sparse coding problems. A D-Wave [3] quantum computer is designed to find optimal solutions to a (discrete) Ising quantum system over a large number of variables via quantum annealing.