  Blind deconvolution (BD), the resolution of a signal and a filter given their
convolution, arises in many applications. Without further constraints, BD is
ill-posed. In practice, subspace or sparsity constraints have been imposed to
reduce the search space, and have shown some empirical success. However,
existing theoretical analysis on uniqueness in BD is rather limited. As an
effort to address the still mysterious question, we derive sufficient
conditions under which two vectors can be uniquely identified from their
circular convolution, subject to subspace or sparsity constraints. These
sufficient conditions provide the first algebraic sample complexities for BD.
We first derive a sufficient condition that applies to almost all bases or
frames. For blind deconvolution of vectors in $\mathbb{C}^n$, with two subspace
constraints of dimensions $m_1$ and $m_2$, the required sample complexity is
$n\geq m_1m_2$. Then we impose a sub-band structure on one basis, and derive a
sufficient condition that involves a relaxed sample complexity $n\geq
m_1+m_2-1$, which we show to be optimal. We present the extensions of these
results to BD with sparsity constraints or mixed constraints, with the sparsity
level replacing the subspace dimension. The cost for the unknown support in
this case is an extra factor of 2 in the sample complexity.
