Fast signal recovery from quadratic measurements

• URL: http://arxiv.org/abs/2010.07012v1
• Date: Sun, 11 Oct 2020 23:36:51 GMT
• Title: Fast signal recovery from quadratic measurements
• Authors: Miguel Moscoso, Alexei Novikov, George Papanicolaou and Chrysoula Tsogka
• Abstract summary: We present a novel approach for recovering a sparse signal from cross-correlated data. The main idea of our proposed approach is to reduce the dimensionality of the problem by recovering only the diagonal of the unknown matrix. Our theory shows that the proposed approach provides exact support recovery when the data is not too noisy, and that there are no false positives for any level of noise.
• Score: 0.0
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: We present a novel approach for recovering a sparse signal from cross-correlated data. Cross-correlations naturally arise in many fields of imaging, such as optics, holography and seismic interferometry. Compared to the sparse signal recovery problem that uses linear measurements, the unknown is now a matrix formed by the cross correlation of the unknown signal. Hence, the bottleneck for inversion is the number of unknowns that grows quadratically. The main idea of our proposed approach is to reduce the dimensionality of the problem by recovering only the diagonal of the unknown matrix, whose dimension grows linearly with the size of the problem. The keystone of the methodology is the use of an efficient {\em Noise Collector} that absorbs the data that come from the off-diagonal elements of the unknown matrix and that do not carry extra information about the support of the signal. This results in a linear problem whose cost is similar to the one that uses linear measurements. Our theory shows that the proposed approach provides exact support recovery when the data is not too noisy, and that there are no false positives for any level of noise. Moreover, our theory also demonstrates that when using cross-correlated data, the level of sparsity that can be recovered increases, scaling almost linearly with the number of data. The numerical experiments presented in the paper corroborate these findings.

Related papers

• On the phase diagram of extensive-rank symmetric matrix denoising beyond rotational invariance [5.058205542605482]
  We make progress towards the understanding of matrix denoising when the hidden signal is a factored matrix $XXintercal$ that is not rotationally invariant. We argue that it is only beyond the transition that factorisation, i.e., estimating $X$ itself, becomes possible up to sign and permutation universality. We also argue that it is only beyond the transition that factorisation, i.e., estimating $X$ itself, becomes possible up to sign and permutation universality.
  arXiv  Detail & Related papers  (2024-11-04T10:50:37Z)
• Gradient Descent Provably Solves Nonlinear Tomographic Reconstruction [60.95625458395291]
  In computed tomography (CT) the forward model consists of a linear transform followed by an exponential nonlinearity based on the attenuation of light according to the Beer-Lambert Law. We show that this approach reduces metal artifacts compared to a commercial reconstruction of a human skull with metal crowns.
  arXiv  Detail & Related papers  (2023-10-06T00:47:57Z)
• Decomposed Diffusion Sampler for Accelerating Large-Scale Inverse Problems [64.29491112653905]
  We propose a novel and efficient diffusion sampling strategy that synergistically combines the diffusion sampling and Krylov subspace methods. Specifically, we prove that if tangent space at a denoised sample by Tweedie's formula forms a Krylov subspace, then the CG with the denoised data ensures the data consistency update to remain in the tangent space. Our proposed method achieves more than 80 times faster inference time than the previous state-of-the-art method.
  arXiv  Detail & Related papers  (2023-03-10T07:42:49Z)
• Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
  We derive an approximate message-passing algorithm (AMP) for the inhomogeneous problem. We identify in particular the existence of a statistical-to-computational gap where known algorithms require a signal-to-noise ratio bigger than the information-theoretic threshold to perform better than random.
  arXiv  Detail & Related papers  (2023-02-13T19:57:17Z)
• GibbsDDRM: A Partially Collapsed Gibbs Sampler for Solving Blind Inverse Problems with Denoising Diffusion Restoration [64.8770356696056]
  We propose GibbsDDRM, an extension of Denoising Diffusion Restoration Models (DDRM) to a blind setting in which the linear measurement operator is unknown. The proposed method is problem-agnostic, meaning that a pre-trained diffusion model can be applied to various inverse problems without fine-tuning.
  arXiv  Detail & Related papers  (2023-01-30T06:27:48Z)
• Shuffled Multi-Channel Sparse Signal Recovery [16.333381000882486]
  We pose it as a signal reconstruction problem where we have lost correspondences between the samples and their respective channels. We show that the problem is equivalent to a structured unlabeled sensing problem, and establish sufficient conditions for unique recovery. We propose a robust reconstruction method that combines sparse signal recovery with robust linear regression for the two-channel case.
  arXiv  Detail & Related papers  (2022-12-14T17:46:17Z)
• Orthogonal Matrix Retrieval with Spatial Consensus for 3D Unknown-View Tomography [58.60249163402822]
  Unknown-view tomography (UVT) reconstructs a 3D density map from its 2D projections at unknown, random orientations. The proposed OMR is more robust and performs significantly better than the previous state-of-the-art OMR approach.
  arXiv  Detail & Related papers  (2022-07-06T21:40:59Z)
• Iterative Correction of Sensor Degradation and a Bayesian Multi-Sensor Data Fusion Method [0.0]
  We present a novel method for inferring ground-truth signal from degraded signals. The algorithm learns a multiplicative degradation effect by performing iterative corrections of two signals. We include theoretical analysis and prove convergence to the ground-truth signal for the noiseless measurement model.
  arXiv  Detail & Related papers  (2020-09-07T13:24:47Z)
• Linear Tensor Projection Revealing Nonlinearity [0.294944680995069]
  Dimensionality reduction is an effective method for learning high-dimensional data. We propose a method that searches for a subspace that maximizes the prediction accuracy while retaining as much of the original data information as possible.
  arXiv  Detail & Related papers  (2020-07-08T06:10:39Z)
• Analytic Signal Phase in $N-D$ by Linear Symmetry Tensor--fingerprint modeling [69.35569554213679]
  We show that the Analytic Signal phase, and its gradient have a hitherto unstudied discontinuity in $2-D $ and higher dimensions. This shortcoming can result in severe artifacts whereas the problem does not exist in $1-D $ signals. We suggest the use of Linear Symmetry phase, relying on more than one set of Gabor filters, but with a negligible computational add-on.
  arXiv  Detail & Related papers  (2020-05-16T21:17:26Z)

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.