This paper investigates conditions under which certain kinds of systems of bilinear equations have a unique structured solution. In particular, we look at when we can recover vectors $\boldsymbol{ w},\boldsymbol{ q}$ from observations of the form \[ y_{ \ell} = <\boldsymbol{ w},\boldsymbol{ b}_{ \ell}><\boldsymbol{ c}_{ \ell},\boldsymbol{ q}>, \quad \ell = 1,\ldots,L, \] where $\boldsymbol{ b}_\ell,\boldsymbol{ c}_\ell$ are known. We show that if $\boldsymbol{ w}\in\mathbb{ C}^{ M_1}$ and $\boldsymbol{ q}\in\mathbb{ C}^{ M_2}$ are sparse, with no more than $K$ and $N$ nonzero entries, respectively, and the $\boldsymbol{ b}_\ell,\boldsymbol{ c}_\ell$ are generic, selected as independent Gaussian random vectors, then $\boldsymbol{ w},\boldsymbol{ q}$ are uniquely determined from \[ L \geq \mathrm{ Const}\cdot (K+N)\log^5(M_1M_2) \] such equations with high probability. The key ingredient in our analysis is a uniform probabilistic bound on how far a random process of the form \[Z(\boldsymbol{ X}) = \sum_{ \ell=1}^L|\boldsymbol{ b}_\ell^*\boldsymbol{ X}\boldsymbol{ c}_\ell|^2 \] deviates from its mean over a set of structured matrices $\boldsymbol{ X}\in\mathcal{ X}$. As both $\boldsymbol{ b}_\ell$ and $\boldsymbol{ c}_\ell$ are random, this is a specialized type of $4$th order chaos; we refer to $Z(\boldsymbol{ X})$ as an { \em empirical chaos process}. Bounding this process yields a set of general conditions for when the map $\boldsymbol{ X}\rightarrow \{ \boldsymbol{ b}_\ell^*\boldsymbol{ X}\boldsymbol{ c}_\ell\}_{ \ell=1}^L$ is a restricted isometry over the set of matrices $\mathcal{ X}$. The conditions are stated in terms of general geometric properties of the set $\mathcal{ X}$, and are explicitly computed for the case where $\mathcal{ X}$ is the set of matrices that are simultaneously sparse and low rank.
Categories: cs.IT math.IT