DISTRIBUTED SENSING OF SIGNALS LINKED BY SPARSE FILTERING

• US 20100177906A1
• Filed: 01/12/2010
• Published: 07/15/2010
• Est. Priority Date: 01/14/2009
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Hormati, Ali, Roy, Olivier, Lu, Yue M., Vetterli, Martin
• Granted Patent: US 8,787,501 B2
• Time in Patent Office: Days
• US Class Current: 381/74
• CPC Class Codes: A61B 5/121 evaluating hearing capacity
• CPC Class Codes: A61B 5/318 Heart-related electrical modalities, e.g. electrocardiography [ECG]
• CPC Class Codes: A61B 5/7257 using Fourier transforms
• CPC Class Codes: G06F 2218/12 Classification; Matching
• CPC Class Codes: H04R 25/407 Circuits for combining signals of a plurality of transducers
• CPC Class Codes: H04R 25/552 Binaural

Abstract

Certain aspects of the present disclosure provide methods for distributed sensing and centralized reconstruction of two correlated signals, modeled as the input and output of an unknown sparse filtering operation.

Claims

1. A method for reconstructing a pair of signals, wherein the first signal is linked to the second signal by an unknown filter, comprising:

observing with a first sensor first samples of the first signal;

observing with a second sensor second samples of the second signal;

exploiting the knowledge that the first and the second signal are linked by a filter for almost surely reconstructing said first signal and said second signal from said first and second samples.

2. The method of claim 1, wherein the number of first and second samples observed is below the minimal number of samples given by the Nyquist relation.

3. The method of claim 2, further comprising:

performing a discrete Fourier transform (DFT) on the samples of the first and second signals to obtain DFT coefficients of the first and second signals.

4. The method of claim 3, further comprising:

almost surely recovering said unknown filter using K+1 said DFT coefficients and an annihilating filter technique.

5. The method of claim 1, further comprising:

receiving discrete Fourier transform (DFT) coefficients of first and second signals, the DFT coefficients including K+1 coefficients for each of the first and second signals and complementary subsets of remaining DFT coefficients for each of the first and second signals;

computing 2K consecutive DFT coefficients of the filter and build a matrix using the received DFT coefficients of the first and second signals and an annihilating filter technique, wherein said matrix is a Toeplitz matrix and has rank K;

obtaining an impulse response of the filter using the computed 2K DFT coefficients, wherein K is a number of non-zero elements of the impulse response of the filter;

reconstructing the first signal using the impulse response of the filter and the received DFT coefficients of the second signal; and

reconstructing the second signal using the impulse response of the filter and the received DFT coefficients of the first signal.

6. An apparatus for reconstructing a pair of signals, wherein the first signal is linked to the second signal by an unknown filter, comprising:

a first receiver configured to observe first samples of the first signal a second receiver configured to receive second samples of the second signal;

a reconstructing circuit configured to almost surely reconstruct said first signal and said second signal from said first and second samples, wherein said reconstructing circuit exploits the knowledge that the first and the second signal are linked by a filter.

7. The apparatus of claim 6, wherein the number of first and second samples observed is below the minimal number of samples given by the Nyquist relation.

8. The apparatus of claim 7, further comprising a calculator configured to perform a discrete Fourier transform (DFT) on the samples of the first and second signals to obtain DFT coefficients of the first and second signals.

9. The apparatus of claim 8, further comprising:

a circuit configured to almost surely recover said unknown filter using K+1 DFT said coefficients, said circuit comprising a calculator using an annihilating filter technique to recover said filter.

10. The apparatus of claim 6, further comprising:

a receiver configured to receive discrete Fourier transform (DFT) coefficients of first and second signals, the DFT coefficients including K+1 coefficients for each of the first and second signals and complementary subsets of remaining DFT coefficients for each of the first and second signals;

a calculator configured to compute 2K consecutive DFT coefficients of the filter and build a matrix using the received DFT coefficients of the first and second signals, wherein said matrix is a Toeplitz matrix and has rank K;

a circuit configured to obtain an impulse response of the filter using the computed 2K DFT coefficients, wherein K is a number of non-zero elements of the impulse response of the filter;

a circuit configured to reconstruct the first signal using the impulse response of the filter and the received DFT coefficients of the second signal; and

a circuit configured to reconstruct the second signal using the impulse response of the filter and the received DFT coefficients of the first signal.

11. A method for signal processing, comprising:

receiving discrete Fourier transform (DFT) coefficients of first and second signals, the DFT coefficients including K+1 coefficients for each of the first and second signals and complementary subsets of remaining DFT coefficients for each of the first and second signals;

computing 2K consecutive DFT coefficients of a filter matrix using the received DFT coefficients of the first and second signals;

obtaining an impulse response of the filter using the computed 2K DFT coefficients, wherein K is a number of non-zero elements of the impulse response of the filter;

reconstructing the first signal using the impulse response of the filter and the received DFT coefficients of the second signal; and

reconstructing the second signal using the impulse response of the filter and the received DFT coefficients of the first signal.

12. The method of claim 11, wherein the first and the second signals are linked by said filter.

13. The method of claim 12, wherein said matrix has rank K.

14. The method of claim 13, wherein said matrix is a Toeplitz matrix.

15. The method of claim 11, wherein the filter comprises a piecewise polynomial filter.

16. The method of claim 11, wherein the filter comprises a piecewise bandlimited filter.

17. An apparatus for signal processing, comprising:

a receiver configured to receive discrete Fourier transform (DFT) coefficients of first and second signals, the DFT coefficients including K+1 coefficients for each of the first and second signals and complementary subsets of remaining DFT coefficients for each of the first and second signals;

a computer configured to compute 2K consecutive DFT coefficients of a filter matrix using the received DFT coefficients of the first and second signals;

a calculator configured to obtain an impulse response of the filter using the computed 2K DFT coefficients, wherein K is a number of non-zero elements of the impulse response of the filter;

a first reconstructing circuit configured to reconstruct the first signal using the impulse response of the filter and the received DFT coefficients of the second signal; and

a second reconstructing circuit configured to reconstruct the second signal using the impulse response of the filter and the received DFT coefficients of the first signal.

18. The apparatus of claim 17, wherein the first and the second signals are linked by said filter.

19. The apparatus of claim 18, wherein said matrix has rank K.

20. The apparatus of claim 19, wherein said matrix is a Toeplitz matrix.

21. The apparatus of claim 17, wherein said apparatus is a headset.

22. The apparatus of claim 17, wherein said apparatus is a monitor for monitoring patient vital signs.

23. The apparatus of claim 17, wherein the filter comprises a piecewise polynomial filter.

24. The apparatus of claim 17, wherein the filter comprises a piecewise bandlimited filter.

25. An apparatus for signal processing, comprising:

means for receiving discrete Fourier transform (DFT) coefficients of first and second signals, the DFT coefficients including K+1 coefficients for each of the first and second signals and complementary subsets of remaining DFT coefficients for each of the first and second signals;

means for computing 2K consecutive DFT coefficients of a filter using the received DFT coefficients of the first and second signals;

means for obtaining an impulse response of the filter using the computed 2K DFT coefficients, wherein K is a number of non-zero elements of the impulse response of the filter;

means for reconstructing the first signal using the impulse response of the filter and the received DFT coefficients of the second signal; and

means for reconstructing the second signal using the impulse response of the filter and the received DFT coefficients of the first signal.

26. The apparatus of claim 25, wherein the filter comprises a piecewise polynomial filter.

27. The apparatus of claim 26, wherein the filter comprises a piecewise bandlimited filter.

28. A computer-program product for signal processing, comprising a computer readable medium comprising instructions executable to:

receive discrete Fourier transform (DFT) coefficients of first and second signals, the DFT coefficients including K+1 coefficients for each of the first and second signals and complementary subsets of remaining DFT coefficients for each of the first and second signals;

compute 2K consecutive DFT coefficients of a filter using the received DFT coefficients of the first and second signals;

obtain an impulse response of the filter using the computed 2K DFT coefficients, wherein K is a number of non-zero elements of the impulse response of the filter;

reconstruct the first signal using the impulse response of the filter and the received DFT coefficients of the second signal; and

reconstruct the second signal using the impulse response of the filter and the received DFT coefficients of the first signal.

29. A headset, comprising:

a receiver configured to receive discrete Fourier transform (DFT) coefficients of first and second signals, the DFT coefficients including K+1 coefficients for each of the first and second signals and complementary subsets of remaining DFT coefficients for each of the first and second signals;

a computer configured to compute 2K consecutive DFT coefficients of a filter using the received DFT coefficients of the first and second signals;

a calculator configured to obtain an impulse response of the filter using the computed 2K DFT coefficients, wherein K is a number of non-zero elements of the impulse response of the filter;

a first reconstructing circuit configured to reconstruct the first signal using the impulse response of the filter and the received DFT coefficients of the second signal;

a second reconstructing circuit configured to reconstruct the second signal using the impulse response of the filter and the received DFT coefficients of the first signal; and

a transducer configured to provide an audio output based on the reconstructed first and second signals.

30. A monitor for monitoring patient vital signs, comprising:

a receiver configured to receive discrete Fourier transform (DFT) coefficients of first and second signals, the DFT coefficients including K+1 coefficients for each of the first and second signals and complementary subsets of remaining DFT coefficients for each of the first and second signals;

a computer configured to compute 2K consecutive DFT coefficients of a filter using the received DFT coefficients of the first and second signals;

a calculator configured to obtain an impulse response of the filter using the computed 2K DFT coefficients, wherein K is a number of non-zero elements of the impulse response of the filter;

a first reconstructing circuit configured to reconstruct the first signal using the impulse response of the filter and the received DFT coefficients of the second signal;

a second reconstructing circuit configured to reconstruct the second signal using the impulse response of the filter and the received DFT coefficients of the first signal; and

a user interface for displaying parameters related to the patient vital signs derived from the reconstructed first and second signals.

31. A method for signal processing, comprising:

sampling of first and second signals to obtain samples of the first and second signals;

performing a discrete Fourier transform (DFT) on the samples of the first and second signals to obtain DFT coefficients of the first and second signals;

sending first L+1 DFT coefficients for each of the first and second signals and complementary subsets of remaining DFT coefficients for each of the first and second signals; and

wherein the first signal is an input in a sparse filter, the second signal is an output of the sparse filter, L≧

K, and K is a number of non-zero elements of an impulse response of the sparse filter.

32. The method of claim 31, further comprising:

performing a windowing operation on the samples of the first and second signals.

33. The method of claim 32, wherein a number of samples of the first signal M₁ and a number of samples of the second signal M₂ satisfy following conditions for an almost sure reconstruction of the first and second signals:

M₁≧

min{K+1,N}, M₂≧

min{K+1,N}, and M₁+M₂≧

min{N+K+1,2N},

where N is a number of samples of the first and second signals after the windowing operation, and min{ } function retrieves a smaller number of two numbers; and

wherein the almost sure reconstruction of the first and second signals assumes that there is a zero probability that the two reconstructed signals are different if the same samples of the first and second signals are used.

34. The method of claim 33, wherein a number of samples of the first signal M₁ and a number of samples of the second signal M₂ satisfy following conditions for an universal reconstruction of the first and second signals:

M₁≧

N, and M₂≧

N, where N is a number of samples of the first and second signals after the windowing operation; and

wherein the universal reconstruction of the first and second signals assumes that the two reconstructed signals cannot be different in any case if the same samples of the first and second signals are used.

35. The method of claim 31, wherein sampling of the first and second signals comprises sampling of one or more frames of the first and second signals.

36. An apparatus for signal processing, comprising:

a sampler configured to sample first and second signals to obtain samples of the first and second signals;

a first circuit configured to performing a discrete Fourier transform (DFT) on the samples of the first and second signals to obtain DFT coefficients of the first and second signals;

a transmitter configured to send first L+1 DFT coefficients for each of the first and second signals and complementary subsets of remaining DFT coefficients for each of the first and second signals; and

wherein the first signal is an input in a sparse filter, the second signal is an output of the sparse filter, L≧

K, and K is a number of non-zero elements of an impulse response of the sparse filter.

37. The apparatus of claim 36, further comprising:

a second circuit configured to perform a windowing operation on the samples of the first and second signals.

38. The apparatus of claim 37, wherein a number of samples of the first signal M₁ and a number of samples of the second signal M₂ satisfy following conditions for an almost sure reconstruction of the first and second signals:

M₁≧

min{K+1,N}, M₂≧

min{K+1,N}, and M₁+M₂≧

min{N+K+1,2N},

where N is a number of samples of the first and second signals after the windowing operation, and min{ } function retrieves a smaller number of two numbers; and

wherein the almost sure reconstruction of the first and second signals assumes that there is a zero probability that the two reconstructed signals are different if the same samples of the first and second signals are used.

39. The apparatus of claim 37, wherein a number of samples of the first signal M₁ and a number of samples of the second signal M₂ satisfy following conditions for an universal reconstruction of the first and second signals:

M₁≧

N, and M₂≧

N, where N is a number of samples of the first and second signals after the windowing operation; and

wherein the universal reconstruction of the first and second signals assumes that the two reconstructed signals cannot be different in any case if the same samples of the first and second signals are used.

40. The apparatus of claim 36, wherein the sampler configured to sample the first and second signals comprises a circuit configured to sample one or more frames of the first and second signals.

41. An apparatus for signal processing, comprising:

means for sampling first and second signals to obtain samples of the first and second signals;

means for performing a discrete Fourier transform (DFT) on the samples of the first and second signals to obtain DFT coefficients of the first and second signals;

means for sending first L+1 DFT coefficients for each of the first and second signals and complementary subsets of remaining DFT coefficients for each of the first and second signals; and

wherein the first signal is an input in a sparse filter, the second signal is an output of the sparse filter, L≧

K, and K is a number of non-zero elements of an impulse response of the sparse filter.

42. The apparatus of claim 41, further comprising:

means for performing a windowing operation on the samples of the first and second signals.

43. The apparatus of claim 42, wherein a number of samples of the first signal M₁ and a number of samples of the second signal M₂ satisfy following conditions for an almost sure reconstruction of the first and second signals:

M₁≧

min{K+1,N}, M₂≧

min{K+1,N}, and M₁+M₂≧

min{N+K+1,2N},

where N is a number of samples of the first and second signals after the windowing operation, and min{ } function retrieves a smaller number of two numbers; and

wherein the almost sure reconstruction of the first and second signals assumes that there is a zero probability that the two reconstructed signals are different if the same samples of the first and second signals are used.

44. The apparatus of claim 42, wherein a number of samples of the first signal M₁ and a number of samples of the second signal M₂ satisfy following conditions for an universal reconstruction of the first and second signals:

M₁≧

N, and M₂≧

N, where N is a number of samples of the first and second signals after the windowing operation; and

wherein the universal reconstruction of the first and second signals assumes that the two reconstructed signals cannot be different in any case if the same samples of the first and second signals are used.

45. The apparatus of claim 41, wherein the means for sampling the first and second signals comprises means for sampling one or more frames of the first and second signals.

46. A computer-program product for signal processing, comprising a computer readable medium comprising instructions executable to:

sample first and second signals to obtain samples of the first and second signals;

perform a discrete Fourier transform (DFT) on the samples of the first and second signals to obtain DFT coefficients of the first and second signals;

send first L+1 DFT coefficients for each of the first and second signals and complementary subsets of remaining DFT coefficients for each of the first and second signals; and

wherein the first signal is an input in a sparse filter, the second signal is an output of the sparse filter, L≧

K, and K is a number of non-zero elements of an impulse response of the sparse filter.

47. A sensing device, comprising:

a sampler configured to sample first and second signals to obtain samples of the first and second signals;

a first circuit configured to performing a discrete Fourier transform (DFT) on the samples of the first and second signals to obtain DFT coefficients of the first and second signals;

a transmitter configured to transmit first L+1 DFT coefficients for each of the first and second signals and complementary subsets of remaining DFT coefficients for each of the first and second signals;

a sensor configured to provide data to be transmitted via the transmitter; and

wherein the first signal is an input in a sparse filter, the second signal is an output of the sparse filter, L≧

K, and K is a number of non-zero elements of an impulse response of the sparse filter.

48. A method for signal processing, comprising:

receiving first L+1 discrete Fourier transform (DFT) coefficients for each of first and second signals;

generating a filter matrix of dimension L×

(L+1) using the received DFT coefficients of the first and second signals;

generating a rank-K filter matrix by setting L−

K+1 smallest singular values of the filter matrix to zero, if a ratio of (K+1)^th singular value of the filter matrix to K^th singular value of the filter matrix is not smaller than a defined threshold value, wherein K is a number of non-zero elements of an impulse response of the filter, and L≧

K;

generating a Toeplitz rank-K filter matrix by averaging coefficients along diagonals of the rank-K filter matrix;

obtaining DFT coefficients of the filter based on elements of the first row and the first column of the Toeplitz rank-K filter matrix, if a ratio of (K+1)^th singular value of the Toeplitz rank-K filter matrix to K^th singular value of the Toeplitz rank-K filter matrix is smaller than the defined threshold value;

computing the impulse response of the filter using the obtained DFT coefficients of the filter;

reconstructing the first signal using the impulse response of the filter and the received DFT coefficients of the second signal; and

reconstructing the second signal using the impulse response of the filter and the received DFT coefficients of the first signal.

49. The method of claim 48, wherein the filter comprises a piecewise polynomial filter.

50. The method of claim 48, wherein the filter comprises a piecewise bandlimited filter.

51. An apparatus for signal processing, comprising:

a receiver configured to receive first L+1 discrete Fourier transform (DFT) coefficients for each of first and second signals;

a first generator configured to generate a filter matrix of dimension L×

(L+1) using the received DFT coefficients of the first and second signals;

a second generator configured to generate a rank-K filter matrix by setting L−

K+1 smallest singular values of the filter matrix to zero, if a ratio of (K+1)^th singular value of the filter matrix to K^th singular value of the filter matrix is not smaller than a defined threshold value, wherein K is a number of non-zero elements of an impulse response of the filter, and L≧

K;

a third generator configured to generate a Toeplitz rank-K filter matrix by averaging coefficients along diagonals of the rank-K filter matrix;

a calculator configured to obtain DFT coefficients of the filter based on elements of the first row and the first column of the Toeplitz rank-K filter matrix, if a ratio of (K+1)^th singular value of the Toeplitz rank-K filter matrix to K^th singular value of the Toeplitz rank-K filter matrix is smaller than the defined threshold value;

a computer configured to compute the impulse response of the filter using the obtained DFT coefficients of the filter;

a first reconstructing circuit configured to reconstruct the first signal using the impulse response of the filter and the received DFT coefficients of the second signal; and

a second reconstructing circuit configured to reconstruct the second signal using the impulse response of the filter and the received DFT coefficients of the first signal.

52. The apparatus of claim 51, wherein the filter comprises a piecewise polynomial filter.

53. The apparatus of claim 51, wherein the filter comprises a piecewise bandlimited filter.

55. The apparatus of claim 51, wherein the filter comprises a piecewise polynomial filter.

56. The apparatus of claim 51, wherein the filter comprises a piecewise bandlimited filter.

54. An apparatus for signal processing, comprising:

means for receiving first L+1 discrete Fourier transform (DFT) coefficients for each of first and second signals;

means for generating a filter matrix of dimension L×

(L+1) using the received DFT coefficients of the first and second signals;

means for generating a rank-K filter matrix by setting L−

K+1 smallest singular values of the filter matrix to zero, if a ratio of (K+1)^th singular value of the filter matrix to K^th singular value of the filter matrix is not smaller than a defined threshold value, wherein K is a number of non-zero elements of an impulse response of the filter, and L≧

K;

means for generating a Toeplitz rank-K filter matrix by averaging coefficients along diagonals of the rank-K filter matrix;

means for obtaining DFT coefficients of the filter based on elements of the first row and the first column of the Toeplitz rank-K filter matrix, if a ratio of (K+1)^th singular value of the Toeplitz rank-K filter matrix to K^th singular value of the Toeplitz rank-K filter matrix is smaller than the defined threshold value;

means for computing the impulse response of the filter using the obtained DFT coefficients of the filter;

means for reconstructing the first signal using the impulse response of the filter and the received DFT coefficients of the second signal; and

means for reconstructing the second signal using the impulse response of the filter and the received DFT coefficients of the first signal.

57. A computer-program product for signal processing, comprising a computer readable medium comprising instructions executable to:

receive first L+1 discrete Fourier transform (DFT) coefficients for each of first and second signals;

generate a filter matrix of dimension L×

(L+1) using the received DFT coefficients of the first and second signals;

generate a rank-K filter matrix by setting L−

K+1 smallest singular values of the filter matrix to zero, if a ratio of (K+1)^th singular value of the filter matrix to K^th singular value of the filter matrix is not smaller than a defined threshold value, wherein K is a number of non-zero elements of an impulse response of the filter, and L≧

K;

generate a Toeplitz rank-K filter matrix by averaging coefficients along diagonals of the rank-K filter matrix;

obtain DFT coefficients of the filter based on elements of the first row and the first column of the Toeplitz rank-K filter matrix, if a ratio of (K+1)^th singular value of the Toeplitz rank-K filter matrix to K^th singular value of the Toeplitz rank-K filter matrix is smaller than the defined threshold value;

compute the impulse response of the filter using the obtained DFT coefficients of the filter;

reconstruct the first signal using the impulse response of the filter and the received DFT coefficients of the second signal; and

reconstruct the second signal using the impulse response of the filter and the received DFT coefficients of the first signal.

58. A headset, comprising:

a receiver configured to receive first L+1 discrete Fourier transform (DFT) coefficients for each of first and second signals;

a first generator configured to generate a filter matrix of dimension L×

(L+1) using the received DFT coefficients of the first and second signals;

a second generator configured to generate a rank-K filter matrix by setting L−

K+1 smallest singular values of the filter matrix to zero, if a ratio of (K+1)^th singular value of the filter matrix to K^th singular value of the filter matrix is not smaller than a defined threshold value, wherein K is a number of non-zero elements of an impulse response of the filter, and L≧

K;

a third generator configured to generate a Toeplitz rank-K filter matrix by averaging coefficients along diagonals of the rank-K filter matrix;

a calculator configured to obtain DFT coefficients of the filter based on elements of the first row and the first column of the Toeplitz rank-K filter matrix, if a ratio of (K+1)^th singular value of the Toeplitz rank-K filter matrix to K^th singular value of the Toeplitz rank-K filter matrix is smaller than the defined threshold value;

a computer configured to compute the impulse response of the filter using the obtained DFT coefficients of the filter;

a first reconstructing circuit configured to reconstruct the first signal using the impulse response of the filter and the received DFT coefficients of the second signal;

a second reconstructing circuit configured to reconstruct the second signal using the impulse response of the filter and the received DFT coefficients of the first signal; and

a transducer configured to provide an audio output based on the reconstructed first and second signals.

59. A monitor for monitoring patient vital signs, comprising:

a receiver configured to receive first L+1 discrete Fourier transform (DFT) coefficients for each of first and second signals;

a first generator configured to generate a filter matrix of dimension L×

(L+1) using the received DFT coefficients of the first and second signals;

a second generator configured to generate a rank-K filter matrix by setting L−

K+1 smallest singular values of the filter matrix to zero, if a ratio of (K+1)^th singular value of the filter matrix to K^th singular value of the filter matrix is not smaller than a defined threshold value, wherein K is a number of non-zero elements of an impulse response of the filter, and L≧

K;

a third generator configured to generate a Toeplitz rank-K filter matrix by averaging coefficients along diagonals of the rank-K filter matrix;

a calculator configured to obtain DFT coefficients of the filter based on elements of the first row and the first column of the Toeplitz rank-K filter matrix, if a ratio of (K+1)^th singular value of the Toeplitz rank-K filter matrix to K^th singular value of the Toeplitz rank-K filter matrix is smaller than the defined threshold value;

a computer configured to compute the impulse response of the filter using the obtained DFT coefficients of the filter;

a first reconstructing circuit configured to reconstruct the first signal using the impulse response of the filter and the received DFT coefficients of the second signal;

a second reconstructing circuit configured to reconstruct the second signal using the impulse response of the filter and the received DFT coefficients of the first signal; and

a user interface for displaying parameters related to the patient vital signs derived from the reconstructed first and second signals.