  Sparsity is a ubiquitous feature of many real world signals such as natural
images and neural spiking activities. Conventional compressed sensing utilizes
sparsity to recover low dimensional signal structures in high ambient
dimensions using few measurements, where i.i.d measurements are at disposal.
However real world scenarios typically exhibit non i.i.d and dynamic structures
and are confined by physical constraints, preventing applicability of the
theoretical guarantees of compressed sensing and limiting its applications. In
this thesis we develop new theory, algorithms and applications for non i.i.d
and dynamic compressed sensing by considering such constraints. In the first
part of this thesis we derive new optimal sampling-complexity tradeoffs for two
commonly used processes used to model dependent temporal structures: the
autoregressive processes and self-exciting generalized linear models. Our
theoretical results successfully recovered the temporal dependencies in neural
activities, financial data and traffic data. Next, we develop a new framework
for studying temporal dynamics by introducing compressible state-space models,
which simultaneously utilize spatial and temporal sparsity. We develop a fast
algorithm for optimal inference on such models and prove its optimal recovery
guarantees. Our algorithm shows significant improvement in detecting sparse
events in biological applications such as spindle detection and calcium
deconvolution. Finally, we develop a sparse Poisson image reconstruction
technique and the first compressive two-photon microscope which uses lines of
excitation across the sample at multiple angles. We recovered
diffraction-limited images from relatively few incoherently multiplexed
measurements, at a rate of 1.5 billion voxels per second.
