Approximate message passing with universal denoising

Patent metadata

Field	Value
Publication number	US-2016358316-A1
Application number	US-201615172534-A
Country	US
Kind code	A1
Filing date	Jun 3, 2016
Priority date	Jun 5, 2015
Publication date	Dec 8, 2016
Grant date	—

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

Therefore, at least the following is claimed:

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; 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 denoising algorithm is a universal denoising algorithm that is agnostic to the specific input statistics.

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

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

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

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

7 . The method of claim 5 , wherein the density function is a mixture model.

8 . The method of claim 3 , 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.

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

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

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

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

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

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

15 . The method of claim 13 , wherein the statistical similarity measure is the l 1 distance.

16 . The method of claim 12 , 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.

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

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

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

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

21 . 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

• G06T5/002 Primary

  Physics · mapped topic