PaperlayerView exact revision on arXiv

Source-linked AI summary

Blind Compressed Sensing

Sivan Gleichman, Yonina C. Eldar

arXiv:1002.2586v2cs.IT

TL;DR

Compressed sensing normally requires knowing the basis in which signals are sparse, while blind compressed sensing seeks recovery without that prior. The paper imposes three basis constraints, proves uniqueness conditions, and proposes recovery methods that perform similarly to standard CS when signals are sufficiently sparse.

  • Problem

    Conventional compressed-sensing recovery requires prior knowledge of the sparsity basis, motivating recovery without that basis.

  • Method

    The paper constrains the unknown basis in three ways and develops uniqueness conditions and recovery procedures, including alternating sparse coding and SVD updates for OBD-BCS.

  • Results

    Under the uniqueness conditions and sufficient sparsity, the proposed methods perform similarly to standard CS using the unknown true basis in synthetic simulations.

  • Takeaways & Limitations

    BCS provides sampling and reconstruction without sparsity-basis knowledge under the presented constraints and conditions.

Abstract

from arXiv · show

The fundamental principle underlying compressed sensing is that a signal, which is sparse under some basis representation, can be recovered from a small number of linear measurements. However, prior knowledge of the sparsity basis is essential for the recovery process. This work introduces the concept of blind compressed sensing, which avoids the need to know the sparsity basis in both the sampling and the recovery process. We suggest three possible constraints on the sparsity basis that can be added to the problem in order to make its solution unique. For each constraint we prove conditions for uniqueness, and suggest a simple method to retrieve the solution. Under the uniqueness conditions, and as long as the signals are sparse enough, we demonstrate through simulations that without knowing the sparsity basis our methods can achieve results similar to those of standard compressed sensing, which relay on prior knowledge of the sparsity basis. This offers a general sampling and reconstruction system that fits all sparse signals, regardless of the sparsity basis, under the conditions and constraints presented in this work.

I. INTRODUCTION

Compressed sensing exploits sparsity to recover high-dimensional signals from few measurements, but conventional recovery requires knowing the sparsity basis. Blind compressed sensing removes that prior through constrained basis models, uniqueness analysis, and recovery algorithms.

  • Compressed sensing: CS measures x as b = Ax with n ≪ m, and sparsity can make recovery unique under conditions on A.For a known basis P, x = Ps with sparse s; sufficiently sparse signals can be uniquely recovered.
  • Recovery methods: Standard CS recovery may use OMP, a suboptimal method that succeeds when signals are sufficiently sparse and A has suitable incoherence.
  • The blind setting: Existing recovery approaches require prior knowledge of the sparsity basis P.
  • Blind compressed sensing: Blind compressed sensing seeks recovery from few measurements when some unknown basis makes the signal sparse, without using that basis for sampling or reconstruction.The framework combines compressed sensing’s low-dimensional measurements with dictionary learning’s lack of basis knowledge.
  • Ill-posedness: Without an additional constraint, BCS is ill posed even with multiple signals sharing an unknown basis.Increasing measurements cannot determine the signal unless their number reaches the signal dimension.
  • Constrained bases: The paper studies finite known basis sets, bases sparse in known dictionaries, and orthogonal block-diagonal bases as constraints enabling uniqueness.
  • Recovery methods: The proposed finite-basis approach solves a CS problem for each candidate basis, while OBD-BCS alternates sparse coding with SVD-based basis updates.
  • Universality: For i.i.d. Gaussian A and any fixed orthogonal P, σ(AP) = n + 1 with probability 1, supporting uniqueness when k ≤ n/2.

B. BCS Problem Formulation

BCS recovers an ensemble of signals that share an unknown sparsity basis, but its unconstrained formulation is non-unique. The problem is related to dictionary learning while differing in its desired output.

  • B. BCS Problem Formulation: A single unconstrained signal is insufficient because every signal is sparse under a basis containing that signal; the framework therefore samples a shared-basis ensemble.
  • B. BCS Problem Formulation: BCS samples multiple signals X = PS using B = AX, where each column of S is k-sparse and n < m.
  • B. BCS Problem Formulation: The goal is to recover X from B and A, not necessarily the particular basis P or sparse matrix S producing X.
  • B. BCS Uniqueness: The unconstrained BCS problem has no unique solution for any measurement matrix, number of signals, or sparsity level.
  • A. Dictionary Learning (DL): Dictionary learning factors B as DS with sparse S, whereas BCS has the constrained dictionary D = AP and seeks X = PS.
  • A. Dictionary Learning (DL): Applying dictionary learning directly is insufficient because it returns D and S, while BCS must postprocess D to retrieve P and then X.
  • A. Dictionary Learning (DL): Dictionary-learning uniqueness relies on a spark condition for D and richness conditions on S, including support coverage and spanning requirements.
  • A. Dictionary Learning (DL): In practice, dictionary-learning algorithms can work with fewer signals than the formal lower bound and with at most k nonzeros per sparse code.

B. BCS Uniqueness

Dictionary-learning ambiguity makes unconstrained BCS non-unique, so the paper imposes basis constraints and derives conditions under which the signal solution becomes unique.

  • Non-uniqueness: Dictionary-learning recovery identifies AP and S only up to a signed permutation, creating ambiguity in retrieving the original basis and signals.
  • Non-uniqueness: The auxiliary problem seeks a basis ˜P satisfying ˜D = A˜P, but rank deficiency in A leaves multiple full-rank basis solutions.
  • Non-uniqueness: Reflecting the null-space component constructs a different basis ˜P2 with the same measurements, demonstrating non-uniqueness.
  • Constraints: The paper considers three constraints: a finite known basis set, dictionary-sparse bases, and orthogonal block-diagonal bases.
  • Finite basis sets: The finite-basis formulation can be unique even for one signal, provided candidate bases remain distinguishable after measurement.
  • Uniqueness conditions: For finite candidate bases, uniqueness requires σ(AP) ≥ 2k for every candidate and k-rank preservation across the basis set.
  • Uniqueness conditions: An i.i.d. Gaussian measurement matrix is k-rank preserving for any fixed finite basis set with probability 1 when k ≤ n/2.
  • Multiple signals: With diverse signals satisfying richness conditions, it is sufficient that candidate products AP differ even under scaling and signed permutation.

B. The F-BCS Method

F-BCS solves a separate compressed-sensing problem for each candidate sparsity basis and selects the basis producing the sparsest representation. With multiple signals, it uses majority selection, while standard CS algorithms provide approximate solutions when sparsity is sufficiently low.

  • F-BCS solves a CS problem for every candidate basis in Ψ.
  • It selects the candidate producing the sparsest representation, or stops when a representation with at most k nonzeros is found if k is known.
  • The recovered signal is x = Pŝ, using the basis associated with the selected sparse representation.
  • For multiple signals, F-BCS selects the sparsity basis by majority across the individual signal solutions.
  • Standard CS algorithms approximate Problems (6) and (7), performing well generally when k is small relative to n.

C. F-BCS Simulation Results

Simulations evaluate F-BCS under noise and increasing sparsity, then describe sparse-basis BCS alternatives. Recovery is perfect in the noiseless F-BCS setting and for k < 8, while algorithmic errors increase with noise or larger sparsity.

  • F-BCS Simulation Results: F-BCS tested five 64 × 64 bases on 100 length-64 signals with up to six nonzeros per sparse coefficient vector.
  • F-BCS Simulation Results: The measurements used a 32 × 64 i.i.d. Gaussian matrix, with noiseless and Gaussian-noise conditions spanning SNRs from 30dB to 5dB.
  • F-BCS Simulation Results: For all noise levels, majority basis selection was correct; noiseless recovery was perfect, while reconstruction error grew with noise.
  • F-BCS Simulation Results: Below 8 nonzeros, recovery was perfect; at higher sparsity levels, false reconstructions and average error increased because OMP may fail despite satisfied uniqueness conditions.
  • Sparse-Basis BCS: A sparse-basis constraint represents P as ΦZ, where Z is sparse and Φ is a known full-row-rank dictionary.
  • Sparse-Basis BCS: For the constrained problem, uniqueness is guaranteed when σ(AΦ) ≥ 2k_pk, and direct recovery requires k_pk to be small relative to n.
  • Sparse-Basis BCS: Sparse K-SVD jointly estimates Z and S, but requires many diverse signals and may fail with too few signals or block-sparse data.

2) Sparse K-SVD:

Sparse K-SVD can solve the constrained BCS formulation, but its performance depends on sparsity and the availability of many diverse signals. The structural constraint uses an orthogonal block-diagonal basis and a measurement matrix formed from orthogonal bases.

  • Sparse K-SVD:: Sparse K-SVD solves constrained BCS by separately recovering k-sparse S and k_p-sparse Z, rather than only their product.The direct method instead recovers the k_pk-sparse product C = ZS.
  • Sparse K-SVD:: For k ≤8, blind and known-basis OMP reconstruction errors are similar; for larger k, the blind method's error is much higher.The comparison uses the direct blind method against OMP with the real, unknown basis P.
  • Sparse K-SVD:: σ(AΦ) = 129 with probability 1, giving uniqueness for k_pk ≤64, or k ≤10, under the stated simulation setting.Error grows earlier because OMP is suboptimal and may fail to find a unique solution; known-basis OMP instead depends on k being small relative to n.
  • Sparse K-SVD:: Sparse K-SVD can improve high-k results when uniqueness holds, but it performs poorly here because the number of signals is smaller than the signal length.The cited simulations for sparse K-SVD used at least 100 times as many signals as signal length.
  • Sparse K-SVD:: The constrained setting uses a 2L-block diagonal orthogonal basis P and a measurement matrix A built as a union of L orthonormal bases.This formulation is motivated by multichannel systems whose channels are sparse under separate bases.

A. Uniqueness Conditions

The uniqueness analysis reduces constrained BCS to a structured dictionary-learning problem. Under richness, spark, orthogonality, and block-structure conditions, the solution is unique.

  • A. Uniqueness Conditions: Problem 8 is equivalent to a dictionary-learning problem when the signals satisfy richness conditions and AP satisfies the required spark condition.The formulation seeks an orthogonal 2L-block diagonal P and a k-sparse S such that B = APS.
  • A. Uniqueness Conditions: A is inter-block diagonal when two blocks satisfy the specified product condition, including the case where A_i^T A_j is 2-block diagonal.This definition is used to state the uniqueness conditions for Problem 9.
  • A. Uniqueness Conditions: Lemma 12 resolves the signed-permutation ambiguity because two orthogonal 2L-block diagonal bases producing the same measurements must differ by the corresponding signed permutation.Without the imposed structures, equality after multiplication by A would not imply equality of the bases because A has a null space.
  • A. Uniqueness Conditions: The uniqueness proof is constructive but impractical, requiring dictionary learning followed by a search over column permutations.A random Gaussian construction followed by Gram–Schmidt can satisfy the theorem's conditions with probability 1.

B. The OBD-BCS Algorithm

OBD-BCS replaces impractical permutation postprocessing with an alternating algorithm that updates sparse codes and the structured basis directly. Its design incorporates the known measurement matrix and block-diagonal prior.

  • B. The OBD-BCS Algorithm: The direct postprocessing approach is impractical because only a tiny fraction of column permutations preserve the required block structure.For m = 16 and L = 2, only 1.58·10^-6% of permutations qualify; for m = 64 and L = 2, the fraction is 1.51 · 10^-34%.
  • B. The OBD-BCS Algorithm: The permutation search is further complicated by dictionary-learning error, noise sensitivity, and the computational cost of suboptimal permutation methods.Even the correct permutation may not yield exactly block-diagonal matrices when the learned dictionary contains error.
  • B. The OBD-BCS Algorithm: OBD-BCS is a practical variation of dictionary learning that solves Problem 8 under the union-of-orthogonal-bases constraint.It is theoretically equivalent to dictionary learning followed by the impractical permutation postprocessing.
  • B. The OBD-BCS Algorithm: OBD-BCS alternates sparse coding, which updates S with P fixed, and basis updating, which updates P with S fixed.Unlike standard dictionary learning, its basis-update step uses the known measurement matrix A and the block-diagonal structure of P.

1) Sparse Coding:

The OBD-BCS algorithm alternates sparse coding with basis updates, using standard compressed sensing for coefficient recovery and SVD-based orthogonal block updates. Each step does not increase its corresponding objective, but convergence to the unique minimum is not proven.

  • 1) Sparse Coding:: Sparse coding fixes P and updates the sparse matrix S by solving separable standard compressed sensing problems, implemented with OMP.The combined measurement matrix D = AP is a union of orthogonal bases, enabling block-based sparse recovery methods.
  • 2) Basis Update:: Basis update fixes S and iteratively updates one orthogonal block of P while holding the remaining blocks fixed.The update decomposes the objective into 2L block subproblems.
  • 2) Basis Update:: When R = S B^T A has full rank, the SVD-based update P_i = V U^T is the unique minimizer of the block objective.If R is rank-deficient, the same update still achieves a minimum, though uniqueness is not established.
  • 2) Basis Update:: Each sparse-coding and basis-update step reduces or preserves its corresponding objective under the stated update conditions.In practice, the sparse-coding guarantee relies on sufficiently small k and an effective CS solver.
  • 2) Basis Update:: The algorithm cannot be proven to converge to the unique minimum, although a unique minimum and non-increasing objective are guaranteed under specific conditions.Simulations nevertheless report strong performance on synthetic data.

C. OBD-BCS Simulations

Simulations evaluate OBD-BCS as the number of signals, sparsity level, and measurement noise vary. With sufficiently many signals and low enough sparsity, reconstruction approaches standard CS using the true basis, while increasing sparsity or noise worsens performance.

  • C. OBD-BCS Simulations: For k = 4, OBD-BCS reconstruction error is averaged over 20 simulations for each signal count N from 150 to 2500.The measurement matrix remains fixed while sparse vectors and orthogonal matrices are regenerated independently.
  • C. OBD-BCS Simulations: For N > 500, OBD-BCS reconstruction is successful and similar to standard CS using the unknown-in-practice true basis.The standard CS reference has an average error of 0.08%.
  • C. OBD-BCS Simulations: Compared with related orthogonal dictionary learning results, OBD-BCS requires only 500 signals under the same measurement dimensions.The cited dictionary-learning method requires at least 640 signals to find about 80% of columns and 1600 to find all columns.
  • C. OBD-BCS Simulations: As k increases, reconstruction error decreases with N until a critical signal count, after which it is nearly constant; both the critical count and constant error increase with k.The same qualitative pattern appears across the tested sparsity levels k ≤ 10.

VII. COMPARATIVE SIMULATION

A comparative simulation tests five reconstruction methods, including true-basis CS, estimated-basis CS, and three BCS methods. OBD-BCS performs similarly to CS with an estimated basis while avoiding the need for training signals, whereas F-BCS and sparse BCS fare worse in the tested setting.

  • VII. COMPARATIVE SIMULATION: The synthetic signals use m = 128, k = 6, N = 2000, and compression ratio L = 2.The basis is an orthogonal 4-block diagonal matrix with additional internal block structure.
  • VII. COMPARATIVE SIMULATION: The comparison evaluates true-basis CS, estimated-basis CS, F-BCS, direct sparse BCS, and OBD-BCS using OMP.The estimated-basis method learns P_D​​L from a training set of 2000 signals.
  • VII. COMPARATIVE SIMULATION: F-BCS performs much worse than the other methods because the signals are 2k-sparse under the identity basis, reducing OMP reconstruction quality.The direct sparse BCS error is also higher because k_p k is not small enough relative to n.
  • VII. COMPARATIVE SIMULATION: OBD-BCS and CS with the estimated basis achieve errors similar to methods using knowledge of the true basis.Unlike estimated-basis CS, OBD-BCS does not require a training set and can operate when only measurements are available.
  • VIII. CONCLUSIONS: The paper presents three basis constraints with uniqueness conditions and recovery methods, with simulation performance similar to true-basis CS when sparsity is small enough.For the structural constraint, enough signals are additionally required.
  • VIII. CONCLUSIONS: Future work includes finding additional uniqueness conditions and weakening the constraints imposed on the sparsity basis.This identifies a stated scope for extending the presented BCS framework.

APPENDIX A

Appendix A establishes that the relevant permutation must preserve the block structure, ultimately forcing it to be L-block diagonal and, in fact, 2L-block diagonal. The proof relies on unions of orthogonal bases and the non-inter-block-diagonal condition on A.

  • Uniqueness: Under the theorem’s assumptions, A ˆP = APQ implies ˆP = PQ.The argument first establishes the required block structure of Q, then uses the orthogonality and block-diagonal structure of P and ˆP.
  • Block structure: Lemma A.1 states that when σ(D) = n + 1, any n orthogonal columns of D come from the same block.This property prevents an orthogonal block from mixing columns drawn from different original blocks.
  • Block structure: Lemma A.2 uses Lemma A.1 to show that if DQ remains a union of L orthonormal bases, then Q belongs to the block-permutation group QB.Such permutations can reorder whole blocks and columns within blocks, but cannot mix blocks.
  • Outer-order preservation: The proof then rules out changes to the outer block order because they would imply that A is inter-block diagonal, contradicting Theorem 11’s conditions.Therefore Q cannot reorder the blocks and must preserve their outer order.
  • Scope and limitation: The argument extends directly from 2L blocks to ML blocks for M > 2, but fails with only L blocks because an additional alternative solution can remain.The extra ambiguity arises because the proof uses the two-block structure to eliminate solutions of the form described in the appendix.

APPENDIX B

Appendix B proves that randomly generated orthogonal blocks almost surely have the required independence and non-inter-block-diagonal properties. These facts establish the structural conditions used by the main uniqueness result.

  • Random-basis properties: Random Gaussian blocks followed by Gram–Schmidt satisfy σ(A) = n + 1 with probability 1.Multiplication by an orthogonal P preserves the relevant statistics, so the same property holds for AP.
  • Random-basis properties: Lemma B.3 states that a randomly generated Gram–Schmidt basis has no column in a given subspace of dimension d < n with probability 1.The proof uses the zero-volume property of lower-dimensional subspaces within the spaces from which successive columns are drawn.
  • Spark condition: Any n + 1 columns are dependent, while smaller cross-block dependencies occur with probability zero, yielding σ(A) = n + 1 with probability 1.The argument separates columns from A1 and the remaining blocks and applies Lemma B.3 to exclude lower-cardinality dependencies.
  • Non-inter-block-diagonal property: The random blocks R1, R2, R3, and R4 all have full rank with probability 1.This full-rank property is used to show that A is not inter-block diagonal with probability 1.

APPENDIX C

Appendix C counts the permutation ambiguities that preserve the 2L-block diagonal structure. The count follows by decomposing each admissible permutation into independent within-block permutations.

  • Permutation structure: For a 2L-block diagonal P, any admissible permutation QD must also be 2L-block diagonal.Lemma 12 implies PQD = ˆP, and because P and ˆP are 2L-block diagonal, QD inherits that structure.
  • Within-block choices: Each block of QD is a permutation of the identity matrix of size m/(2L).The block size determines the number of possible within-block permutations.
  • Counting ambiguities: There are (m/(2L))! possibilities for each block, giving [(m/(2L))!]^(2L) total choices across the 2L blocks.The passage presents the per-block count and states that the total is obtained across all 2L blocks.
Loading 1002.2586v2…