Method and apparatus for on-line compressed sensing
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
H04N-007/12
H04N-011/02
H04N-011/04
출원번호
US-0091340
(2006-10-25)
등록번호
US-8687689
(2014-04-01)
국제출원번호
PCT/US2006/041621
(2006-10-25)
§371/§102 date
20080819
(20080819)
국제공개번호
WO2007/050680
(2007-05-03)
발명자
/ 주소
Baraniuk, Richard
Baron, Dror Z.
Duarte, Marco F.
Elnozahi, Mohamed
Wakin, Michael B.
Davenport, Mark A.
Laska, Jason N.
Tropp, Joel A.
Massoud, Yehia
Kirolos, Sami
Ragheb, Tamer
출원인 / 주소
William Marsh Rice University
대리인 / 주소
24IP Law Group
인용정보
피인용 횟수 :
4인용 특허 :
8
초록▼
A typical data acquisition system takes periodic samples of a signal, image, or other data, often at the so-called Nyquist/Shannon sampling rate of two times the data bandwidth in order to ensure that no information is lost. In applications involving wideband signals, the Nyquist/Shannon sampling ra
A typical data acquisition system takes periodic samples of a signal, image, or other data, often at the so-called Nyquist/Shannon sampling rate of two times the data bandwidth in order to ensure that no information is lost. In applications involving wideband signals, the Nyquist/Shannon sampling rate is very high, even though the signals may have a simple underlying structure. Recent developments in mathematics and signal processing have uncovered a solution to this Nyquist/Shannon sampling rate bottlenck for signals that are sparse or compressible in some representation. We demonstrate and reduce to practice methods to extract information directly from an analog or digital signal based on altering our notion of sampling to replace uniform time samples with more general linear functionals. One embodiment of our invention is a low-rate analog-to-information converter that can replace the high-rate analog-to-digital converter in certain applications involving wideband signals. Another embodiment is an encoding scheme for wideband discrete-time signals that condenses their information content.
대표청구항▼
1. A method for obtaining a compressed representation of a continuous-time signal s, the method comprising: taking a sequence y of measurements for the continuous-time signal s, wherein the continuous-time signal s is of sparsity k with respect to a dictionary of continuous-time functions, wherein k
1. A method for obtaining a compressed representation of a continuous-time signal s, the method comprising: taking a sequence y of measurements for the continuous-time signal s, wherein the continuous-time signal s is of sparsity k with respect to a dictionary of continuous-time functions, wherein k is a positive integer, wherein said taking a sequence y of measurements comprises: supplying the continuous time signal s to an analog filter in order to obtain a filtered signal, wherein an impulse response of the analog filter is incoherent with respect to the dictionary of continuous-time functions; andsampling the filtered signal with a sampler at a sampling rate determined by the sparsity k of the continuous-time signal s, wherein the sampling rate is less than a Nyquist frequency of the continuous-time signal s. 2. A method according to claim 1, further comprising: providing the sequence y of measurements to a signal processor; andcomputing with said signal processor an approximate reconstruction of the continuous-time signal s from said the sequence y. 3. A method according to claim 2, wherein said signal processor uses a greedy pursuit method to compute said approximate reconstruction of the continuous-time signal s. 4. A method according to claim 1, wherein the dictionary includes a subdictionary that represents a signal class of interest, the method further comprising: providing said set of measurements y to a signal processor; anddetecting whether the continuous-time signal s contains signal energy within the signal class by operating on the sequence y of measurements. 5. A method according to claim 1, wherein said continuous-time signal s belongs to a signal class that is parameterized by one or more parameters, the method further comprising: estimating the one or more parameters for the continuous-time signal s based on the sequence y of measurements. 6. A method according to claim 1, wherein the dictionary of continuous-time functions comprises one or more of the following types of functions: Dirac deltas, sinusoidal functions, wavelets, linear-FM chirps, chirplets, binary chirp sequence signals, polynomial functions, phase coded waveforms, Barker code pulses, pseudorandom noise (PN) sequences, and communication signals. 7. A method for estimating the value of a functional ƒ on a continuous-time signal s, the method comprising: acquiring a sequence y of measurements of the continuous-time signal s, wherein the continuous-time signal s is of sparsity k with respect to a dictionary of continuous-time functions, wherein k is a positive integer, wherein each of the measurements y(n) corresponds to the value of a corresponding linear functional φn on the continuous-time signal s, wherein the number of measurements in the sequence y is determined by the sparsity k, wherein the number of measurements in the sequence y is less than a product of a time interval of acquisition and a Nyquist rate of the continuous-time signal s; andprocessing the sequence y of measurements with a signal processor to obtain an estimate of the value of the functional ƒ on the continuous-time signal s. 8. A method according to claim 7, wherein said processing the sequence y of measurements comprises: computing an approximate reconstruction of said continuous-time signal s based on the sequence y, andevaluating said functional ƒ on said approximate reconstruction. 9. A method according to claim 7, wherein said functional ƒ is designed according to a signal processing task desired on the continuous-time signal s. 10. A method according to claim 9, wherein said signal processing task comprises: detection of whether the continuous-time signal s contains significant signal energy in a signal class of interest, orclassification of the continuous-time signal s into one of a plurality of signal classes. 11. A method according to claim 9, wherein said number of measurements in the sequence y is selected according to the signal processing task desired. 12. A method according to claim 7, wherein said processing of said set of measurements y comprises the use of one or more of the following: a sparse approximation algorithm, l0 minimization, l1 minimization, a greedy algorithm, an optimization algorithm, a complexity-regularization algorithm, a homotopy-based algorithm, a group testing algorithm and a belief propagation algorithm. 13. An apparatus for obtaining a compressed representation of a discrete-time signal s of length n, the apparatus comprising: a multiplier configured to mix the discrete-time signal s with a pseudorandom sequence to obtain a modulated discrete-time signal, wherein the discrete-time signal s is of sparsity k with respect to a dictionary of discrete-time signals, wherein k is a positive integer;a filter configured to filter the modulated discrete-time signal to obtain a filtered discrete-time signal;a downsampler configured to obtain a sequence y of m samples of the filtered discrete-time signal, with m being less than n. 14. An apparatus according to claim 13, wherein said pseudorandom sequence alternates pseudorandomly between two amplitude states. 15. An apparatus according to claim 13, wherein the downsampler is configured to downsample the filtered discrete-time signal uniformly in time. 16. An apparatus for estimating the value of a functional ƒ of a discrete-time signal s of length n, the apparatus comprising: means for acquiring a sequence y of m measurements of the discrete-time signal s, wherein the discrete-time signal s is of sparsity k with respect to a dictionary of discrete-time signals, wherein k is a positive integer, wherein m is less than n, wherein the sequence y of m measurements is characterized by the expression y=Φs, wherein the rows of the m×n matrix Φ are incoherent with respect to the dictionary of discrete-time signals;means for estimating the value of said functional ƒ of the discrete-time signal s from the sequence y. 17. An apparatus for obtaining a compressed representation of a continuous-time signal s, the apparatus comprising: a mixer configured to mix the continuous-time signal s with a pseudorandom sequence in the analog domain to obtain a modulated signal, wherein the continuous-time signal s is of sparsity k with respect to a dictionary of continuous-time functions, wherein k is a positive integer;an analog filter configured to filter the modulated signal to obtain a filtered signal; anda sampling device configured to sample the filtered signal at a sampling rate less than a Nyquist rate of the continuous-time signal s in order to obtain a sequence y of measurements. 18. An apparatus according to claim 17, wherein said pseudorandom sequence is configured to alternate pseudorandomly between two amplitude states. 19. An apparatus according to claim 17, wherein said sampling device is configured to perform said sampling uniformly in time. 20. An apparatus for estimating a value of a functional ƒ of a continuous-time signal s, the apparatus comprising: means for acquiring a sequence y of measurements of the continuous-time signal s, wherein the continuous-time signal s is of sparsity k with respect to a dictionary of continuous-time functions, wherein k is a positive integer, wherein each of the measurements y(n) corresponds to the value of a corresponding linear functional φn on the continuous-time signal s, wherein the number of measurements in the sequence y is determined by the sparsity of the continuous-time signal s, wherein the number of measurements is less than a product of a time interval of acquisition and a Nyquist rate of the continuous-time signal s;means for processing the sequence y of measurements to obtain an estimate of the value of said functional ƒ of the continuous-time signal s. 21. A method according to claim 2, wherein said signal processor uses one or more of the following methods to compute said approximate reconstruction of the continuous-time signal s: a sparse approximation algorithm; l0 minimization; l1 minimization; a greedy algorithm; an optimization algorithm; a complexity-regularization algorithm; a homotopy-based algorithm; a group testing algorithm; a Viterbi algorithm; and a belief propagation algorithm. 22. A method according to claim 4, wherein said detecting includes: performing a plurality of iterations of a greedy pursuit algorithm to obtain a coefficient vector with respect to the dictionary; anddetermining whether a restriction of the coefficient vector to a subspace corresponding to the subdictionary has co norm greater than a threshold. 23. A method according to claim 1, wherein the filter is configured to pseudo-randomly change the phases of spectral components of the continuous-time signal s. 24. A method according to claim 1, wherein the filter includes a plurality of inter-digital transducers and a piezoelectric substrate. 25. A method according to claim 1, wherein the filter includes a bank of parallel low-order analog subfilters and a respective plurality of switches, wherein the switches are configured to randomly connect different combinations of the subfilters over time. 26. A method for obtaining a compressed representation of a continuous-time signal s, the method comprising: obtaining a sequence y of measurements of the continuous-time signal s, wherein the continuous-time signal s is of sparsity k with respect to a dictionary of continuous-time functions, wherein k is a positive integer wherein said obtaining comprises: mixing the continuous-time signal s with a pseudorandom sequence in the analog domain to obtain a modulated signal;supplying the modulated signal to an analog low-pass filter to obtain a filtered signal;sampling the filtered signal to obtain the sequence y of measurements, wherein said sampling is performed at a sampling rate less than a Nyquist rate of the continuous-time signal s. 27. A method according to claim 26, wherein the pseudorandom sequence changes states at a rate that is on the same order as the Nyquist rate of the continuous-time signal s. 28. A method according to claim 26, wherein the pseudorandom sequence takes values from the set {a,−a}, where a is a positive value. 29. A method according to claim 26, further comprising: generating the pseudorandom sequence based on a known seed using a linear feedback shift register (LFSR). 30. A method according to claim 26, wherein the filter is an integrator circuit. 31. A method according to claim 26, wherein the dictionary comprises a set of Gabor atoms. 32. A method according to claim 26, further comprising: providing the sequence y of measurements to a signal processor; andcomputing with said signal processor an approximate reconstruction of the continuous-time signal s from the sequence y. 33. A method according to claim 32, wherein said signal processor uses a greedy pursuit method to compute said approximate reconstruction of the continuous-time signal s. 34. A method according to claim 32, wherein said signal processor uses one or more of the following methods to compute said approximate reconstruction of the continuous-time signal s: a sparse approximation algorithm; l0 minimization; l1 minimization; a greedy algorithm; an optimization algorithm; a complexity-regularization algorithm; a homotopy-based algorithm; a group testing algorithm; a Viterbi algorithm; and a belief propagation algorithm. 35. A method according to claim 26, wherein the dictionary includes a subdictionary that represents a signal class of interest, the method further comprising: providing the sequence y of measurements y to a signal processor; anddetecting whether the continuous-time signal s contains a significant amount of signal energy within the signal class by operating on the sequence y of measurements. 36. A method according to claim 35, wherein said detecting includes: performing a plurality of iterations of a greedy pursuit algorithm to obtain a coefficient vector with respect to the dictionary; anddetermining whether a restriction of the coefficient vector to a subspace corresponding to the subdictionary has ∞ norm greater than a threshold. 37. A method according to claim 26, wherein the continuous-time signal s belongs to a signal class that is parameterized by one or more parameters, the method further comprising: estimating the one or more parameters for the continuous-time signal s based on the sequence y of measurements. 38. A method according to claim 26, wherein the dictionary of continuous-time functions comprises one or more of the following types of functions: Dirac deltas, sinusoidal functions, wavelets, linear-FM chirps, chirplets, binary chirp sequence signals, polynomial functions, phase coded waveforms, Barker code pulses, pseudorandom noise (PN) sequences, and communication signals. 39. A method according to claim 7, wherein the functional ƒ is a statistic of the continuous-time signal s. 40. A method according to claim 7, wherein the functional ƒ is a linear functional. 41. A method according to claim 9, wherein said signal processing task comprises one or more of the following: dimensionality reduction, parameter estimation and manifold learning. 42. An apparatus according to claim 13, further comprising: means for computing an approximate reconstruction of the discrete-time signal s from the sequence y of m measurements. 43. An apparatus according to claim 42, wherein the means for computing employs a greed pursuit algorithm to compute the approximate reconstruction. 44. An apparatus according to claim 13, wherein the downsampler is configured to downsample the filtered discrete-time signal non-uniformly in time. 45. A method according to claim 17, wherein the sampling rate is proportional to the sparsity k of the continuous-time signal s. 46. A method comprising: receiving a sequence y of m measurements of a signal s, wherein the signal s is of sparsity k with respect to a dictionary Ψ of functions, wherein k is a positive integer, wherein m is a positive integer, wherein the sequence y of m measurements is characterized by the expression y=Φs, wherein Φ is a linear operator on a space including the linear span of the dictionary Ψ;performing one or more iterations of a greedy pursuit algorithm on the sequence y of m measurements to obtain a sparse approximation ΦΨα of the signal s, wherein α is an n-element coefficient vector, wherein n is an integer greater than m;restricting the coefficient vector α to a subspace corresponding to a signal class of interest;comparing an ∞ norm of the restricted coefficient vector to a threshold to determine whether the signal s contains significant signal energy in the signal class. 47. A method according to claim 46, wherein the greedy pursuit algorithm is a matching pursuit algorithm. 48. A method according to claim 46, wherein the signal s is a continuous-time signal. 49. A method according to claim 46, wherein the signal s is a discrete-time signal. 50. A method comprising: receiving a sequence y of m measurements of a signal s, wherein the signal s is of sparsity k with respect to a dictionary Ψ of functions, wherein k is a positive integer, wherein m is a positive integer, wherein the sequence y of m measurements is characterized by the expression y=Φs, wherein Φ is a linear operator on a space include the linear span of the dictionary Ψ;for each of L subdictionaries of the dictionary Ψ, performing a greedy pursuit algorithm on the sequence y of measurements with respect to the corresponding subdictionary, wherein each of the L subdictionaries represents a corresponding signal class of interest;determining which of the signal classes the signal s belongs to by determining which of the L performances of the greedy pursuit algorithm converges with smallest iteration index. 51. A method according to claim 50, wherein the greedy pursuit algorithm is a matching pursuit algorithm. 52. A method according to claim 50, wherein the signal s is a continuous-time signal. 53. A method according to claim 50, wherein the signal s is a discrete-time signal.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (8)
Dawes Robert L. (Allen TX), Adaptive processing system having an array of individually configurable processing components.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.