  This paper tackles algorithmic and theoretical aspects of dictionary learning
from incomplete and random block-wise image measurements and the performance of
the adaptive dictionary for sparse image recovery. This problem is related to
blind compressed sensing in which the sparsifying dictionary or basis is viewed
as an unknown variable and subject to estimation during sparse recovery.
However, unlike existing guarantees for a successful blind compressed sensing,
our results do not rely on additional structural constraints on the learned
dictionary or the measured signal. In particular, we rely on the spatial
diversity of compressive measurements to guarantee that the solution is unique
with a high probability. Moreover, our distinguishing goal is to measure and
reduce the estimation error with respect to the ideal dictionary that is based
on the complete image. Using recent results from random matrix theory, we show
that applying a slightly modified dictionary learning algorithm over
compressive measurements results in accurate estimation of the ideal dictionary
for large-scale images. Empirically, we experiment with both space-invariant
and space-varying sensing matrices and demonstrate the critical role of spatial
diversity in measurements. Simulation results confirm that the presented
algorithm outperforms the typical non-adaptive sparse recovery based on
offline-learned universal dictionaries.
