Estimating a Signal Based on Samples Derived from Random Projections

A computer-readable memory medium storing program instructions, wherein the program instructions are executable by one or more processors to:

• (a) receive a data value, wherein the data value provides information regarding a signal to be estimated;
• (b) generate a random vector that corresponds to the data value;
• (c) multiply the data value and the sampling vector to obtain a current back projection;
• (d) compute a first intermediate vector that represents an average of the current back projection and previous back projections;
• (e) apply a transformation to the first intermediate vector to determine a second intermediate vector;
• (f) identify a set of index positions where the second intermediate vector attains its k largest values in terms of absolute value, wherein k is a positive integer;
• (g) compute an estimate for the transformation of the signal by solving a system of equations based on the set of index positions, the received data value, previously received data values, the sampling vector and previously generated sampling vectors;
• (h) apply an inverse of the transformation to said estimate for the transformation to determine an estimate of the signal;
• and
• (i) store the estimate of the signal in memory.

A computer system for estimating a signal, the computer system comprising:

• a processor;
• and memory storing program instructions that are executable by the processor to:
• (a) receive a data value, wherein the data value provides information regarding a signal to be estimated;
• (b) multiply the data value and a corresponding sampling vector to obtain a current back projection;
• (c) compute a first intermediate vector that represents an average of the current back projection and previous back projections;
• (d) apply a transformation to the first intermediate vector to determine a second intermediate vector;
• (e) identify a set of index positions where the second intermediate vector attains its k largest values in terms of absolute value, wherein k is a positive integer;
• (f) compute a fourth intermediate vector by applying an inverse of the transformation to the third intermediate vector;
• (g) compute a dot product of the fourth intermediate vector with the random vector;
• (h) repeat (a) through (h) until a separation between the dot product and the corresponding data value smaller than a threshold value;
• (k) compute an estimate of the signal using the set of index positions, the received data value, previously received data values, the sampling vector and previous sampling vectors;
• and
• (l) store the signal estimate in the memory.