Encoder blind combinatorial compressed sensing
- URL: http://arxiv.org/abs/2004.05094v2
- Date: Mon, 19 Jul 2021 08:30:29 GMT
- Title: Encoder blind combinatorial compressed sensing
- Authors: Michael Murray, Jared Tanner
- Abstract summary: We consider the problem of designing a decoder to recover a set of sparse codes from their linear measurements alone.
The contribution of this paper is a computationally efficient decoding algorithm, Decoder-Expander Based Factorisation.
- Score: 5.177947445379688
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: In its most elementary form, compressed sensing studies the design of
decoding algorithms to recover a sufficiently sparse vector or code from a
lower dimensional linear measurement vector. Typically it is assumed that the
decoder has access to the encoder matrix, which in the combinatorial case is
sparse and binary. In this paper we consider the problem of designing a decoder
to recover a set of sparse codes from their linear measurements alone, that is
without access to encoder matrix. To this end we study the matrix factorisation
task of recovering both the encoder and sparse coding matrices from the
associated linear measurement matrix. The contribution of this paper is a
computationally efficient decoding algorithm, Decoder-Expander Based
Factorisation, with strong performance guarantees. In particular, under mild
assumptions on the sparse coding matrix and by deploying a novel random encoder
matrix, we prove that Decoder-Expander Based Factorisation recovers both the
encoder and sparse coding matrix at the optimal measurement rate with high
probability and from a near optimal number of measurement vectors. In addition,
our experiments demonstrate the efficacy and computational efficiency of our
algorithm in practice. Beyond compressed sensing our results may be of interest
for researchers working in areas such as linear sketching, coding theory and
matrix compression.
Related papers
- Localized statistics decoding: A parallel decoding algorithm for quantum low-density parity-check codes [3.001631679133604]
We introduce localized statistics decoding for arbitrary quantum low-density parity-check codes.
Our decoder is more amenable to implementation on specialized hardware, positioning it as a promising candidate for decoding real-time syndromes from experiments.
arXiv Detail & Related papers (2024-06-26T18:00:09Z) - Learning Linear Block Error Correction Codes [62.25533750469467]
We propose for the first time a unified encoder-decoder training of binary linear block codes.
We also propose a novel Transformer model in which the self-attention masking is performed in a differentiable fashion for the efficient backpropagation of the code gradient.
arXiv Detail & Related papers (2024-05-07T06:47:12Z) - A blockBP decoder for the surface code [0.0]
We present a new decoder for the surface code, which combines the accuracy of the tensor-network decoders with the efficiency and parallelism of the belief-propagation algorithm.
Our decoder is therefore a belief-propagation decoder that works in the degenerate maximal likelihood decoding framework.
arXiv Detail & Related papers (2024-02-07T13:32:32Z) - Block-encoding structured matrices for data input in quantum computing [0.0]
We show how to construct block encoding circuits based on an arithmetic description of the sparsity and pattern of repeated values of a matrix.
The resulting circuits reduce flag qubit number according to sparsity, and data loading cost according to repeated values.
arXiv Detail & Related papers (2023-02-21T19:08:49Z) - Machine Learning-Aided Efficient Decoding of Reed-Muller Subcodes [59.55193427277134]
Reed-Muller (RM) codes achieve the capacity of general binary-input memoryless symmetric channels.
RM codes only admit limited sets of rates.
Efficient decoders are available for RM codes at finite lengths.
arXiv Detail & Related papers (2023-01-16T04:11:14Z) - Neural Belief Propagation Decoding of Quantum LDPC Codes Using
Overcomplete Check Matrices [60.02503434201552]
We propose to decode QLDPC codes based on a check matrix with redundant rows, generated from linear combinations of the rows in the original check matrix.
This approach yields a significant improvement in decoding performance with the additional advantage of very low decoding latency.
arXiv Detail & Related papers (2022-12-20T13:41:27Z) - Variational Autoencoders for Studying the Manifold of Precoding Matrices
with High Spectral Efficiency [47.187609203210705]
We look at how to use a variational autoencoder to find a precoding matrix with a high Spectral Efficiency (SE)
Our objective is to create a less time-consuming algorithm with minimum quality degradation.
arXiv Detail & Related papers (2021-11-23T11:45:45Z) - Robust 1-bit Compressive Sensing with Partial Gaussian Circulant
Matrices and Generative Priors [54.936314353063494]
We provide recovery guarantees for a correlation-based optimization algorithm for robust 1-bit compressive sensing.
We make use of a practical iterative algorithm, and perform numerical experiments on image datasets to corroborate our results.
arXiv Detail & Related papers (2021-08-08T05:28:06Z) - Unfolding Neural Networks for Compressive Multichannel Blind
Deconvolution [71.29848468762789]
We propose a learned-structured unfolding neural network for the problem of compressive sparse multichannel blind-deconvolution.
In this problem, each channel's measurements are given as convolution of a common source signal and sparse filter.
We demonstrate that our method is superior to classical structured compressive sparse multichannel blind-deconvolution methods in terms of accuracy and speed of sparse filter recovery.
arXiv Detail & Related papers (2020-10-22T02:34:33Z) - Pruning Neural Belief Propagation Decoders [77.237958592189]
We introduce a method to tailor an overcomplete parity-check matrix to (neural) BP decoding using machine learning.
We achieve performance within 0.27 dB and 1.5 dB of the ML performance while reducing the complexity of the decoder.
arXiv Detail & Related papers (2020-01-21T12:05:46Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.