  This paper discusses the recovery of an unknown signal $x\in \mathbb{R}^L$
through the result of its convolution with an unknown filter $h \in
\mathbb{R}^L$. This problem, also known as blind deconvolution, has been
studied extensively by the signal processing and applied mathematics
communities, leading to a diversity of proofs and algorithms based on various
assumptions on the filter and its input. Sparsity of this filter, or in
contrast, non vanishing of its Fourier transform are instances of such
assumptions. The main result of this paper shows that blind deconvolution can
be solved through nuclear norm relaxation in the case of a fully unknown
channel, as soon as this channel is probed through a few $N \gtrsim \mu^2_m
K^{1/2}$ input signals $x_n = C_n m_n$, $n=1,\ldots,N,$ that are living in
known $K$-dimensional subspaces $C_n$ of $\mathbb{R}^L$. This result holds with
high probability on the genericity of the subspaces $C_n$ as soon as $L\gtrsim
K^{3/2}$ and $N\gtrsim K^{1/2}$ up to log factors. Our proof system relies on
the construction of a certificate of optimality for the underlying convex
program. This certificate expands as a Neumann series and is shown to satisfy
the conditions for the recovery of the matrix encoding the unknowns by
controlling the terms in this series. An incidental consequence of the result
of this paper, following from the lack of assumptions on the filter, is that
nuclear norm relaxation can be extended from blind deconvolution to blind
super-resolution, as soon as the unknown ideal low pass filter has a
sufficiently large support compared to the ambient dimension $L$. Numerical
experiments supporting the theory as well as its application to blind
super-resolution are provided.
