Method and Apparatus for Distributed Compressed Sensing

• US 20080129560A1
• Filed: 08/08/2007
• Published: 06/05/2008
• Est. Priority Date: 05/10/2005
• Status: Active Grant

• Current Assignee: Rice University
• Original Assignee: Rice University
• Inventors: Baraniuk, Richard G., Baron, Dror Z., Wakin, Michael B., Duarte, Marco F., Davenport, Mark, Sarvotham, Shriram
• Granted Patent: US 7,511,643 B2
• Time in Patent Office: Days
• US Class Current: 341/87
• CPC Class Codes: G06F 2218/22 Source localisation; Inverse modelling
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H04N 19/60 using transform coding

Abstract

A method for approximating a plurality of digital signals or images using compressed sensing. In a scheme where a common component x_c of said plurality of digital signals or images an innovative component x_i of each of said plurality of digital signals each are represented as a vector with m entries, the method comprises the steps of making a measurement y_c, where y_c comprises a vector with only n_i entries, where n_i is less than m, making a measurement y_i for each of said correlated digital signals, where y_i comprises a vector with only n_i entries, where n_i is less than m, and from each said innovation components y_i, producing an approximate reconstruction of each m-vector x_i using said common component y_c and said innovative component y_i.

Claims

1-15. -15. (canceled)

16. A method for reconstructing a plurality of signals, images, or video sequences, comprising the steps of:

taking M_j measurements of each signal x_j among the plurality of J signals;

reconstructing the plurality of signals by seeking possible values for the plurality of signals that explain the measurements.

17. A method for reconstructing a plurality of signals, images, or video sequences according to claim 16, wherein said method reconstructs said signal approximately.

18. A method for reconstructing a plurality of signals, images, or video sequences according to claim 16,

wherein in said scheme each of the plurality of signals are measured using the same number M of measurements.

19. A method for reconstructing a plurality of signals, images, or video sequences according to claim 16,

wherein in said scheme for each signal x_J among the plurality of J signals there exists an N-parameter representation of length N and the M_j measurements of x_j are obtained by projecting x_j onto a plurality of measurement vectors.

20. A method for reconstructing a plurality of signals, images, or video sequences according to claim 16,

wherein in said scheme for each signal x_j among the plurality of J signals there exists a discrete representation of length N and the M_j measurements of x_j are obtained by projecting x_j onto a plurality of measurement vectors.

21. A method for reconstructing a plurality of signals, images, or video sequences according to claim 16,

wherein in said scheme for each signal x_j among the plurality of J signals there exists a discrete representation of length N and the number of measurements M_j taken of x_j is smaller than N.

22. A method for reconstructing a plurality of signals, images, or video sequences according to claim 16,

wherein in said scheme the M_j measurements of each of signals x_j among the plurality of J signals are encoded.

23. A method for reconstructing a plurality of signals, images, or video sequences according to claim 22, wherein said scheme the M_j measurements of each of signals x_j among the plurality of J signals are encoded digitally.

24. A method for reconstructing exactly or approximately a plurality of signals, images, or video sequences according to claim 19,

wherein in said scheme the M_j measurements of each signal x_j among the plurality of J signals are measured using different sets of measurement vectors.

25. A method for reconstructing exactly or approximately a plurality of signals, images, or video sequences according to claim 18,

wherein in said scheme the M measurements of each of the plurality of signals are measured using the same plurality of measurement vectors.

26. A method for reconstructing a plurality of signals, images, or video sequences according to claim 19,

wherein in said scheme the M_j measurements of each signal x_j among a plurality of J signals consist of a subset of measurements obtained from projections onto the same set of measurement vectors for each signal and another subset of measurements obtained from projections onto different measurement vectors.

27. An apparatus according to claim 19 wherein said means for measuring measures said plurality of signals using an incoherent measurement matrix.

28. A method for reconstructing a plurality of signals, images, or video sequences according to claim 19,

wherein in said scheme of obtaining M_j measurements of each signal x_j among a plurality of J signals comprises projecting x_j onto at least one of the following types of sequences:

random sequences, Bernoulli-distributed sequences, Gaussian-distributed sequences, coding scheme sequences, Fourier sequences, Hadamard sequences, cyclic sequences, Toeplitz sequences, and sparse sequences.

29. A method for reconstructing exactly or approximately a plurality of signals, images, or video sequences according to claim 16,

wherein said reconstruction method reconstructs each signal x_j among said plurality of J signals independently of reconstruction of other signals among said plurality.

30. A method for reconstructing exactly or approximately a plurality of signals, images, or video sequences according to claim 16,

wherein in said reconstruction method of seeking possible values for said plurality of signals that explain the measurements relies on any possible mathematical model for said plurality of signals.

32. A method for reconstructing exactly or approximately a plurality of signals, images, or video sequences according to claim 16,

wherein said reconstruction method relies on a mathematical model where each of said plurality of signals consist of a linear combination of identical signal elements under different coefficients.

33. A method for reconstructing exactly or approximately a plurality of signals, images, or video sequences according to claim 30,

wherein said reconstruction method relies on a mathematical model where each of said plurality of signals consist of a linear combination of identical signal elements under different coefficients.

34. A method for reconstructing exactly or approximately a plurality of signals, images, or video sequences according to claim 16,

wherein said reconstruction method relies on a mathematical model where each of said plurality of signals consists of a sum of a common signal component and an additional components that consist of a linear combination of identical signal elements under different coefficients.

35. A method for reconstructing exactly or approximately a plurality of signals, images, or video sequences according to claim 16,

wherein said reconstruction method relies on mathematical model where each of said plurality of signals consists of a sum of a common signal component and a set of additional signal components being different for each of the plurality of signals.

36. A method for reconstructing a video sequence according to claim 35,

wherein said reconstruction method relies on mathematical model where each of said plurality of different additional signal components represents motion between different image frames of the video sequence.

37. A method for reconstructing a plurality of signals, images, or video sequences according to claim 16,

wherein said reconstruction method relies on at least one of the following algorithms:

1₀, 1₁, Basis Pursuit with Denoising, LARS, LASSO, Simultaneous Orthogonal Matching Pursuit or Trivial Pursuit.

38. A method for reconstructing exactly or approximately a plurality of signals, images, or video sequences according to claim 32, wherein said reconstruction method relies on a non-iterative greedy algorithm based on matched filtering to identify the said identical signal elements.

39. A method for reconstructing exactly or approximately a plurality of signals, images, or video sequences according to claim 34,

wherein said reconstruction method relies on the iterative sequential estimation of the common and additional components of each of said plurality of signals.

40. A method for reconstructing exactly or approximately a plurality of signals, images, or video sequences according to claim 35,

wherein said reconstruction method relies on the iterative sequential estimation of the common and additional components of each of said plurality of signals.

41. An apparatus according to claim 16 wherein said means for measuring comprises a plurality of sensors in any modality.

42. An apparatus according to claim 30 wherein said plurality of sensors comprise at least one selected from the group of:

cameras, acoustic and temperature sensors.

31. A method for reconstructing exactly or approximately a plurality of digital signals, images, or video sequences comprising the steps of:

estimating a common component of said plurality of digital signals;

estimating measurements generated by innovations of each of said plurality of digital signals;

constructing approximations of said innovations of each of said plurality of digital signals; and

obtaining an estimate of at least one signal from said plurality of digital signals as the sum of said estimate of said common component and estimates of at least one innovation component of said at least one signal.

49. A method for reconstructing exactly or approximately a plurality of signals, images, or video sequences according to claim 31,

wherein said estimation of the common component and at least one innovation component uses 1₁ reconstruction, where the measurements of the plurality of signals are constrained to explain all signal components while having minimal norm.

50. A method for reconstructing exactly or approximately a plurality of signals, images, or video sequences according to claim 49,

wherein said norm can be weighted differently for each among the single common component and the plurality of J innovation components.

43. A method for detecting the presence or absence of a signal of interest in at least one of a plurality of signals, images, or video sequences, comprising the steps of:

taking M_j measurements of each signal x_j among the plurality of J signals;

determining if the measurements are more consistent with the presence or absence of the signal of interest.

44. A method as in claim 43, wherein said step of determining if the measurements are more consistent with the presence or absence of the signal of interest comprises using any reconstruction method to obtain an approximation of the signal from which one can more easily test if the measurements are more consistent with the presence or absence of the signal of interest.

45. A method as in claim 43, wherein said step of determining if the measurements are more consistent with the presence or absence of the signal of interest comprises using a greedy reconstruction method such as Orthogonal Matching Pursuit or Matching Pursuit, but stopping the algorithm after a small number of iterations, to obtain an approximation of the signal from which one can more easily test if the measurements are more consistent with the presence or absence of the signal of interest.

46. A method for estimating the value of a function that depends on one or more of a plurality of signals, images, or video sequences, comprising the steps of:

taking M_j measurements of each signal x_j among the plurality of J signals;

determining the value of the function that is most consistent with the measurements.

47. A method as in claim 46, wherein said step of determining the value of the function that is most consistent with the measurements comprises using any reconstruction method to obtain an approximation of the signal from which one can then directly estimate the function of interest.

48. A method as in claim 46, wherein said step of determining the value of the function that is most consistent with the measurements comprises using a greedy reconstruction method such as Orthogonal Matching Pursuit or Matching Pursuit, but stopping the algorithm after a small number of iterations, to obtain an approximation of the signal from which one can then directly estimate the function of interest.