2016/08/30 by Ali Ahmed, Ahmed, Ali, Felix Krahmer +3
Computer Science · Engineering · Mathematics · #Blind Source Separation Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #Random Matrices and Applications #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1608.08370
openalex publication_date 2016/08/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 \boldsymbolw,\boldsymbolq from observations of the form yℓ = , ℓ = 1,…,L, where \boldsymbolb_ℓ,\boldsymbolc_ℓ are known. We show that if \boldsymbolw∈ℂM1 and \boldsymbolq∈ℂM2 are sparse, with no more than K and N nonzero entries, respectively, and the \boldsymbolb_ℓ,\boldsymbolc_ℓ are generic, selected as independent Gaussian random vectors, then \boldsymbolw,\boldsymbolq are uniquely determined from L ≥ Const⋅ (K+N)log5(M1M2) 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(\boldsymbolX) = ∑ℓ=1L|\boldsymbolb_ℓ^*\boldsymbolX\boldsymbolc_ℓ|2 deviates from its mean over a set of structured matrices \boldsymbolX\inX. As both \boldsymbolb_ℓ and \boldsymbolc_ℓ are random, this is a specialized type of 4th order chaos; we refer to Z(\boldsymbolX) as an \em empirical chaos process. Bounding this process yields a set of general conditions for when the map \boldsymbolX→ \\boldsymbolb_ℓ^*\boldsymbolX\boldsymbolc_ℓ\ℓ=1L is a restricted isometry over the set of matrices X. The conditions are stated in terms of general geometric properties of the set X, and are explicitly computed for the case where X is the set of matrices that are simultaneously sparse and low rank.