PaperlayerView exact revision on arXiv

Source-linked AI summary

Distributed Compressive Sensing: A Deep Learning Approach

Hamid Palangi, Rabab Ward, Li Deng

arXiv:1508.04924v3cs.LGcs.CV

TL;DR

MMV compressed-sensing methods commonly assume joint sparsity, though sparse vectors may instead have unknown dependencies. The paper uses those dependencies to guide greedy reconstruction and reports that its method outperforms SOMP and several Bayesian methods on two real-world datasets.

  • Problem

    Many MMV reconstruction methods assume joint sparsity, although sparse vectors may not be exactly jointly sparse and may still depend on one another.

    Source: A. Problem Statement · p. 2

  • Method

    A two-step greedy algorithm uses conditional nonzero probabilities based on previous vectors’ residuals to select support entries, then estimates their values.

    Source: B. Proposed Method · p. 2

  • Results

    On two real-world datasets, the method outperformed SOMP and several Bayesian MMV methods.

    Source: B. Proposed Method · p. 3, §V · p. 11

  • Takeaways & Limitations

    The authors present deep sequence modeling as a proof of concept for improving MMV solvers, especially for more complex sparsity patterns.

    Source: §V · p. 12

    When training samples are expensive to collect or insufficient, the authors recommend using other sparse reconstruction methods.

    Source: §V · p. 12

Abstract

from arXiv · show

Various studies that address the compressed sensing problem with Multiple Measurement Vectors (MMVs) have been recently carried. These studies assume the vectors of the different channels to be jointly sparse. In this paper, we relax this condition. Instead we assume that these sparse vectors depend on each other but that this dependency is unknown. We capture this dependency by computing the conditional probability of each entry in each vector being non-zero, given the "residuals" of all previous vectors. To estimate these probabilities, we propose the use of the Long Short-Term Memory (LSTM)[1], a data driven model for sequence modelling that is deep in time. To calculate the model parameters, we minimize a cross entropy cost function. To reconstruct the sparse vectors at the decoder, we propose a greedy solver that uses the above model to estimate the conditional probabilities. By performing extensive experiments on two real world datasets, we show that the proposed method significantly outperforms the general MMV solver (the Simultaneous Orthogonal Matching Pursuit (SOMP)) and a number of the model-based Bayesian methods. The proposed method does not add any complexity to the general compressive sensing encoder. The trained model is used just at the decoder. As the proposed method is a data driven method, it is only applicable when training data is available. In many applications however, training data is indeed available, e.g. in recorded images and videos.

I. INTRODUCTION · A. Problem Statement

The paper asks whether training data can reveal dependencies among MMV sparse vectors that are not necessarily jointly sparse, and whether the decoder can exploit them without adding encoder complexity. The introduction situates this problem within compressive sensing and existing MMV recovery methods.

I. INTRODUCTION

  • Compressive sensing acquires M < N measurements instead of N signal samples and recovers a sparse signal from the underdetermined measurements.The introduction describes applications including medical imaging, geophysical data analysis, computational biology, remote sensing, and communications.Source: §I · p. 1
  • In MMV recovery, L sparse vectors are reconstructed from L measurement vectors; applications include magnetoencephalography, array processing, channel equalization, and cognitive radio.This is also called distributed compressive sensing.Source: §I · p. 1
  • Standard MMV methods typically assume a common support across vectors, and jointly solving MMV can improve uniqueness guarantees over solving each vector independently.The introduction presents a necessary and sufficient uniqueness condition under the joint-sparsity assumption [7].Source: §I · pp. 1–2
  • Existing MMV approaches include greedy methods such as SOMP, relaxed mixed-norm minimization, and Bayesian methods,,.The choice among them depends on the application's requirements.Source: §I · p. 2

A. Problem Statement

  • Prior MMV reconstruction methods do not use training data, although many applications have large amounts of similar data available.Examples include repeated camera recordings, images from the same class, and EEG recordings from different brain regions.Source: A. Problem Statement · p. 2
  • The central problem is to learn from training data dependencies among MMV sparse vectors that are not jointly sparse, then use those dependencies for reconstruction.The paper notes that noise or different sources can produce different sparsity patterns even when the vectors remain dependent.Source: A. Problem Statement · p. 2
  • The encoder is intended to remain simple and general, without added complexity or adaptation; the decoder may be more complex.The authors do not seek to optimize the sensing matrix or sparsifying basis for the training data, an important constraint for low-power sensors.Source: A. Problem Statement · p. 2

B. Proposed Method · C. Related Work · II. RNN WITH LSTM CELLS

The paper uses an LSTM to model dependencies among MMV sparse vectors and guide greedy reconstruction, situating the approach among structured, Bayesian, neural, and temporal compressed-sensing methods.

B. Proposed Method

  • At each iteration, the greedy solver estimates each column’s nonzero-entry probabilities conditioned on previous columns’ residuals, selects the most probable entry, then estimates support values by least squares.The residual matrix is R_j = Y − AS_j; least squares uses y_i and the atoms of A belonging to that column’s support.Source: B. Proposed Method · p. 2
  • An RNN with LSTM cells and a softmax layer estimates the conditional probabilities; cross-entropy training is performed once, and the trained model is then used on unseen test data at the decoder.The encoder’s main computation remains multiplication by a random matrix, preserving low-power encoding; the added computations are at the decoder.Source: B. Proposed Method · pp. 2–3
  • With one LSTM layer, the proposed method significantly outperforms MMV baselines such as SOMP and Bayesian methods MT-BCS [12] and T-SBL [13] on two real-world datasets.The authors describe it as a deep-learning, bottom-up method that learns structure from raw data, despite using a greedy selection that need not be optimal.Source: B. Proposed Method · pp. 2–3

C. Related Work

  • Prior structured compressed-sensing work includes measurement-saving signal models, structural reviews, Bayesian CS, and MMV methods MT-BCS, SBL, and T-SBL.The cited MMV methods exploit shared task priors or correlated rows, while T-SBL addresses temporally correlated sources.Source: C. Related Work · pp. 3–4
  • Neural approaches include NNOMP, NWSOMP and DSN-WSOMP, and feedforward regression [18]; temporal sparse recovery also uses residual-based, SBL, and dynamic-Lasso methods,,.The cited DSN-WSOMP approach assumes joint sparsity of S.Source: C. Related Work · p. 4

II. RNN WITH LSTM CELLS

  • Treating sparse-vector columns as a sequence lets an RNN predict sparsity patterns across channels, while LSTM memory cells address the vanishing-gradient difficulty of learning long-term dependencies.The proposed LSTM uses input, forget, and output gates, a cell state, and peephole connections; its input weights map residual vectors into feature space.Source: §II · pp. 4–5

III. PROPOSED METHOD · A. High Level Picture

LSTM-CS uses residual sequences to estimate nonzero-entry probabilities, then iteratively selects supports and reconstructs sparse vectors. Its trained model is used at the decoder, while the offline training computations do not affect solver runtime.

A. High Level Picture

  • LSTM-CS initializes sparse estimates to zero and each channel’s residual to its measurement, then uses LSTM weights and memory to model residual features and dependencies.The algorithm also initializes the support set as empty.Source: A. High Level Picture · p. 5
  • A transformation U maps each gated memory output into sparse-vector space, and channel-wise softmax estimates each entry’s probability of being nonzero.Source: A. High Level Picture · p. 5
  • For each channel, LSTM-CS adds the entry with the highest probability to its support, then estimates the sparse vector by solving a least-squares problem.Source: A. High Level Picture · p. 5
  • After each estimate, the algorithm computes a new residual from the measurement and reconstructed signal, and feeds that residual to the LSTM at the next iteration.Source: A. High Level Picture · p. 5
  • LSTM-CS stops when residuals are small enough or after N iterations, where N is the sparse-vector dimension.Source: A. High Level Picture · p. 5
  • Offline data preparation and learning are performed once and do not affect solver runtime; the proposed solver is almost as fast as greedy sparse-reconstruction algorithms.Source: A. High Level Picture · p. 5

B. Training Data Generation

Training data is generated by turning sparse reconstruction into sequential classification: residuals from progressively removing nonzero entries are paired with one-hot labels for the next entry to predict. The procedure is repeated across samples and channels, with a maximum number of nonzeros assumed because the true count is unknown.

B. Training Data Generation

  • The training procedure treats reconstruction as classification followed by least squares, using residual vectors and corresponding sparse-vector labels for supervised training.Given a sparse vector s with k nonzero entries, it computes y using (3), removes the largest entry, and forms a residual from the omitted contribution.Source: B. Training Data Generation · p. 6
  • The residual after removing the largest entry is paired with a one-hot label at the second-largest entry, whose contribution is used to predict its location.The pair is (r, s0), where s0 is 1 at index k1 and zero elsewhere.Source: B. Training Data Generation · p. 6
  • After each predicted entry is removed, the new residual is paired with a one-hot label for the next-largest entry, and this process continues until no nonzeros remain.For example, after removing the second-largest entry, the residual is paired with a label at the third-largest entry's index.Source: B. Training Data Generation · p. 6
  • The same procedure generates training samples for each channel, and generation assumes a maximum number of nonzeros per channel because the actual count is unknown.Source: B. Training Data Generation · p. 6

C. Learning Method

The model is trained by minimizing cross-entropy over training data. Training uses backpropagation through time with Nesterov updates and implementation choices tailored to the known channel-sequence length.

C. Learning Method

  • Training minimizes cross-entropy between the model’s conditional-probability output and one-hot targets over the training data.The optimized parameters include the LSTM weights, biases, and transformation matrix.Source: C. Learning Method · p. 6
  • The parameters are optimized with backpropagation through time and the Nesterov method, folding the LSTM back across channels to compute sequence-wide gradients.The update uses the cost-function gradient, a learning rate, and a scheduled momentum parameter.Source: C. Learning Method · pp. 6–7
  • Mini-batch training updates all parameters per batch, while gradient clipping addresses gradient explosion.The implementation uses a fixed learning rate and sets the momentum parameter to 0.9 for the first and last 10% of updates and 0.995 for the middle 80%.Source: C. Learning Method · pp. 6–7
  • The implementation removes peephole connections and forget gates because sequence length is known and cell states are reset to zero at each sequence’s start.The paper also states that preserving column order makes precise sequence timing less important, and that removing these components reduces the number of parameters to tune.Source: C. Learning Method · p. 7

IV. EXPERIMENTAL RESULTS AND DISCUSSION · A. MNIST Dataset

The experiments evaluate LSTM-CS on MNIST against other MMV reconstruction methods, with results reporting improved reconstruction performance, including across noise levels and measurement settings.

IV. EXPERIMENTAL RESULTS AND DISCUSSION

  • The experiments address performance with differing sparsity patterns, correlated vectors, runtime, and noise robustness.They use reconstruction error based on the actual and recovered sparse matrices; experiments ran on an Intel Core i7 CPU with 16 GB RAM.Source: §IV · p. 7

A. MNIST Dataset

  • The MNIST test encodes four 24×24 digit images in four channels, using 50% random measurements per 12×12 block and Gaussian noise at SNR ≃46dB.The test set contains 40 images, with 10 images for each digit 0–3; the 200-image training set excludes test images.Source: A. MNIST Dataset · pp. 7–8
  • LSTM-CS significantly outperforms the other MMV reconstruction algorithms compared on MNIST.The paper attributes this to existing solvers’ reliance on joint sparsity and LSTM’s ability to capture each sparse vector’s structure.Source: Figure 4 · p. 8, A. MNIST Dataset · pp. 8–9
  • For simple sparsity patterns such as digit 1, all methods reconstruct well, while accuracy degrades for more complex patterns such as digit 0.The paper illustrates these reconstructions for four MNIST test images.Source: Figure 5 · p. 9, A. MNIST Dataset · p. 9
  • At SNR = 6 dB, MT-BCS, LSCS, and PCSBL-GAMP degrade significantly, while T-SBL, NWSOMP, and LSTM-CS degrade less; at 20 and 26 dB, LSTM-CS, T-SBL, and PCSBL-GAMP are close, with LSTM-CS slightly better.At SNR = 46 dB, LSTM-CS with 512 cells and 200 training images performs better than the other methods.Source: A. MNIST Dataset · pp. 9–10, Figure 7 · p. 10
  • At M = 36, LSTM-CS performs better when trained with more cells or more training data than the model used at M = 72.The tested variants used 512 or 1024 cells, or two or four times more training data.Source: A. MNIST Dataset · p. 9, Figure 6 · p. 10
  • The phase-transition experiment reports improved reconstruction performance with LSTM-CS, using a recovery criterion of NMSE ≤ 0.6 for more than 90% of test images.It evaluates 800 sparse vectors formed from 50 images per channel across four channels and four blocks per image.Source: A. MNIST Dataset · p. 10
  • With n = 144, an LSTM-CS model using 512 cells and 400 training images improves reconstruction performance over the other methods as the number of random measurements varies.The other methods use settings similar to those described earlier.Source: A. MNIST Dataset · p. 10

B. Natural Images Dataset

The natural-image experiments evaluated LSTM-CS on the MSR Cambridge dataset using blockwise reconstruction and DCT and wavelet transforms. LSTM-CS was reported to run almost as fast as greedy algorithms.

B. Natural Images Dataset

  • Experiments used 10 test images from three classes of the MSR Cambridge dataset, with each 64×64 image divided into 8×8 blocks.Four blocks were encoded jointly (L = 4), with N = 64 entries per sparse vector and M = 32 measurements, or 50%.Source: B. Natural Images Dataset · pp. 10–11
  • LSTM-CS was compared with SOMP, T-SBL, MT-BCS, and NWSOMP using DCT and three-level Haar wavelet transforms.Training used 55 images per class and validation used 5 images per class, with neither set overlapping the 10 test images; LSTM-CS was trained for 15 epochs.Source: B. Natural Images Dataset · p. 11
  • In the paper’s MMV experiments, the proposed algorithm was almost as fast as greedy algorithms for reconstruction, with each plotted CPU-time point averaging reconstruction time per sparse vector across all 8×8 blocks in 10 test images.TMSBL, a faster version of T-SBL, improved T-SBL’s CPU time but remained slower than other reconstruction methods.Source: B. Natural Images Dataset · p. 11

V. CONCLUSIONS AND FUTURE WORK

The paper presents an MMV reconstruction method that learns sparse-vector structure without assuming joint sparsity, and reports that it outperforms SOMP and several Bayesian methods on two real-world datasets. It frames LSTM-based sequence modeling as a proof of concept, with training-data availability and future extensions defining its scope.

V. CONCLUSIONS AND FUTURE WORK

  • On two real-world datasets, the proposed method outperformed SOMP and a number of Bayesian model-based MMV methods.The paper reports this comparison without providing numerical results in the supplied conclusion passages.Source: §V · p. 11
  • The method reconstructs MMV sparse vectors by learning their structure rather than relying on the commonly used joint-sparsity assumption.The authors note that they did not use multiple LSTM layers or advanced training methods such as dropout.Source: §V · pp. 11–12
  • The work is a proof of concept that LSTM sequence modeling can improve MMV solvers, especially for sparsity patterns more complicated than DCT or Wavelet patterns, as shown on MNIST.Source: §V · p. 12
  • When collecting training samples is expensive or enough samples are unavailable, the authors recommend using other sparse-reconstruction methods.Source: §V · p. 12
  • Future work includes bidirectional LSTM-CS, nonlinear distributed compressive sensing, video compressive sensing, and EEG-signal compressive sensing.The proposed applications exploit correlation among video frames or among EEG channels.Source: §V · p. 12

APPENDIX A EXPRESSIONS FOR THE GRADIENTS · A. Output Weights U · B. Output Gate

The appendix supplies final gradient expressions for training LSTM-CS, omitting full derivations. It specifies parameter updates and gradients for output weights and the output gate.

APPENDIX A EXPRESSIONS FOR THE GRADIENTS

  • The appendix presents final gradient expressions needed to train LSTM-CS, while omitting their full derivations.The expressions follow from the cost function in (12).Source: Appendix A · p. 12
  • Parameter gradients use the Nesterov method to update LSTM-CS model parameters.The appendix gives a general cost-gradient format for weight matrices and bias vectors in the architecture.Source: Appendix A · p. 12

A. Output Weights U

  • For output weights U, the appendix relates each channel’s vector z(t) to its input v(t) by z(t) = Uv(t).It presents the gradient expressions using channel-index notation; during training, the one-hot vectors for s0 make β equal to 1.Source: Appendix A · p. 12
  • The output-weight gradient expressions combine the preceding relations and define e(t) starting from the L-th channel.The appendix uses t for the channel index in place of τ.Source: Appendix A · p. 12

APPENDIX A EXPRESSIONS FOR THE GRADIENTS

  • The final gradient sums contributions over mini-batch samples and channels.The appendix notes that subscripts r and i are omitted for simplicity.Source: Appendix A · p. 13

B. Output Gate

  • For the output gate, the appendix provides gradient expressions for recurrent connections, input and peephole connections, and gate biases.The input and peephole matrices are identified as W1 and Wp1, respectively.Source: B. Output Gate · p. 13

C. Input Gate

The input-gate section lists recurrent, input, and peephole connections, as well as bias values b3.

C. Input Gate

D. Forget Gate

The forget-gate section identifies four parameter groups: recurrent connections, input connections, peephole connections, and bias values.

D. Forget Gate

E. Input without Gating (yg(t)) · F. Error signal backpropagation

The section presents connection-related equations for input without gating and describes backpropagating error signals through time using equations.

E. Input without Gating (yg(t))

  • The subsection introduces equations for recurrent connections, input connections, and bias values in the input-without-gating setting.The supplied passages identify these equation topics but do not include the equations themselves.Source: E. Input without Gating (yg(t)) · pp. 14–15

F. Error signal backpropagation

Related papers

Loading 1508.04924v3…