  We derive near optimal performance guarantees for subsampled blind
deconvolution. Blind deconvolution is an ill-posed bilinear inverse problem and
additional subsampling makes the problem even more challenging. Sparsity and
spectral flatness priors on unknown signals are introduced to overcome these
difficulties. While being crucial for deriving desired near optimal performance
guarantees, unlike the sparsity prior with a nice union-of-subspaces structure,
the spectral flatness prior corresponds to a nonconvex cone structure, which is
not preserved by elementary set operations. This prohibits the operator arising
in subsampled blind deconvolution from satisfying the standard restricted
isometry property (RIP) at near optimal sample complexity, which motivated us
to study other RIP-like properties. Combined with the performance guarantees
derived using these RIP-like properties in a companion paper, we show that
subsampled blind deconvolution is provably solved at near optimal sample
complexity by a practical algorithm.
