Approximate message passing with universal denoising

Patent metadata

Field	Value
Publication number	US-10140249-B2
Application number	US-201615172534-A
Country	US
Kind code	B2
Filing date	Jun 3, 2016
Priority date	Jun 5, 2015
Publication date	Nov 27, 2018
Grant date	Nov 27, 2018

Abstract

Various examples of methods and systems are provided for approximate message passing with universal denoising. In one example, a method includes applying an approximate message passing (AMP) conversion framework to a plurality of substantially linear measurements to produce a plurality of scalar measurements; applying a denoiser algorithm to the plurality of scalar measurements to generate a plurality of denoised scalar measurements; and applying a conversion term to the plurality of denoised scalar measurements to convert the plurality of denoised scalar measurements to a plurality of denoised substantially linear measurements.

First claim

The invention claimed is:

1. A method comprising:
applying, using processing circuitry including a processor and memory, an approximate message passing (AMP) conversion framework to a plurality of substantially linear measurements to produce a plurality of scalar measurements;
applying, using the processing circuitry, a denoiser algorithm to the plurality of scalar measurements to generate a plurality of denoised scalar measurements, where the denoiser algorithm is a universal denoiser algorithm that is agnostic to input statistics of the plurality of scalar measurements and denoises as well based on error metric criteria comprising at least one of squared error, ell infinity (l ∞ ) error, ell1 (l 1 ) error, and ell_p (l p ) error; and
applying, using the processing circuitry, a conversion term to the plurality of denoised scalar measurements to convert the plurality of denoised scalar measurements to a plurality of denoised substantially linear measurements.

2. The method of claim 1 , wherein the universal denoiser algorithm involves context quantization for subsequencing, where subsequences are denoised using a denoiser designed for independent and identically distributed subsequences.

3. The method of claim 2 , further comprising weighting the contexts prior to context quantization.

4. The method of claim 2 , wherein the denoiser designed for independent and identically distributed subsequences comprises density function estimation followed by an optimal Bayesian algorithm for denoising signals with that density function.

5. The method of claim 4 , wherein the optimal Bayesian algorithm is optimized for p-norm errors.

6. The method of claim 4 , wherein the density function is a mixture model.

7. The method of claim 2 , further comprising estimating a density function of the current subsequence based at least in part upon symbols from other subsequences, and denoising the current subsequence using the density function.

8. The method of claim 7 , wherein the symbols from other subsequences comprise symbols whose contexts are similar to the contexts corresponding to symbols of the current subsequence.

9. The method of claim 8 , wherein weights of the symbols decay exponentially or linearly based on how far the symbol is from the middle of the context.

10. The method of claim 9 , wherein a rate of decay of the weights is a function of an estimated signal to noise ratio.

11. The method of claim 2 , further comprising merging statistically similar subsequences prior to independent and identically distributed subsequence denoising.

12. The method of claim 11 , wherein a statistical similarity measure of the statistically similar subsequences is measured using empirical distributions of two subsequences.

13. The method of claim 12 , wherein the statistical similarity measure is a Kullback Leibler divergence or a symmetric version thereof.

14. The method of claim 12 , wherein the statistical similarity measure is an l 1 distance.

15. The method of claim 11 , further comprising a model selection criterion to compare a current model and a new model after merging, and accepting or rejecting the merging based upon the comparison.

16. The method of claim 15 , wherein the model selection criterion is a minimum description length criterion.

17. The method of claim 2 , wherein the context quantization involves clustering using a k-means algorithm.

18. The method of claim 1 , wherein a generalized approximate message passing (GAMP) framework is used to account for one or more noise distributions.

19. The method of claim 18 , wherein the one or more noise distributions is estimated empirically.

20. The method of claim 1 , wherein the applied denoising algorithm is a sliding window denoiser.

Assignees

• Univ North Carolina State

Inventors

• Baron Dror
• Ma Yanting
• Zhu Junan

Classifications

• G06F17/11 Primary

  for solving equations {, e.g. nonlinear equations, general mathematical optimization problems (optimization specially adapted for a specific administrative, business or logistic context G06Q10/04)} · CPC title