Systems and method for determining frequency coefficients of signals

Abstract

A system for determining the frequency coefficients of a one or multi-dimensional signal that is sparse in the frequency domain includes determining the locations of the non-zero frequency coefficients, and then determining values of the coefficients using the determined locations. If N is total number of frequency coefficients across the one or more dimension of the signal, and if R is an upper bound of the number of non-zero ones of these frequency coefficients, the systems requires up to (O (R log(R) (N))) samples and has a computation complexity of up to O (R log2(R) log (N). The system and the processing technique are stable to low-level noise and can exhibit only a small probability of failure. The frequency coefficients can be real and positive or they can be complex numbers.

What is claimed is: 
     
       1. A method for identifying magnitudes of frequency components of a signal ƒ(x), the method comprising:
 obtaining at a receiver a first plurality of sets of samples of a signal received by an antenna or a sensor, each set comprising a plurality of samples of the signal ƒ(x) obtained using a respective sampling interval based on a respective shuffling parameter, cardinality of each set being greater than an upper bound (R) of a number of non-zero frequency components of the signal ƒ(x) and less than a number of samples N of the signal ƒ(x) according to a Nyquist rate, wherein obtaining each set of signal samples comprises subsampling by the receiver the signal at a respective rate less than the Nyquist rate, and at least one set of signal samples determines a support set  ; and 
 computing by a processor an initial set of frequency coefficients {circumflex over (ƒ)} 0  using the support set   and frequency coefficients of the first plurality of sets of signal samples, the support set   identifying indices of the non-zero frequency coefficients of the signal ƒ(x). 
 
     
     
       2. The method of  claim 1 , wherein obtaining the first plurality of sets of signal samples comprises accessing from memory T sets of signal samples, wherein:
 T is on the order of O(1) or on the order of O(R log R  N); and 
 a t-th set of signal samples, wherein index t ranges from 1 through T, comprises P (t)  signal samples, P (t)  being greater than R and smaller than N. 
 
     
     
       3. The method of  claim 1 , wherein obtaining the first plurality of sets of signal samples comprises:
 determining the number of samples (N) of the signal ƒ(x) according to the Nyquist rate, and obtaining the upper bound (R) of the number of non-zero frequency components of the signal; 
 selecting a number of sets (T), wherein T is on the order of O(1) or on the order of O(R log R  N), and selecting T recovery parameters P (t) , wherein index t ranges from 1 through T; 
 for each recovery parameter P (t) , sampling the signal ƒ(x) at P (t)  distinct locations, providing the first plurality of T sets of signal samples, each sample set having P (t)  samples. 
 
     
     
       4. The method of  claim 1 , wherein computing the initial set of frequency coefficients {circumflex over (ƒ)} 0  comprises multiplying the first plurality of sets of signal samples by: (i) a discrete Fourier transform (DFT) matrix F comprising T DFT submatrices, each submatrix having a size P (t) , and index t ranging from 1 through T, and (ii) a binary matrix B based on the support set  . 
     
     
       5. The method of  claim 1 , further comprising:
 generating a set of frequency coefficients {circumflex over (ƒ)} using a binary matrix B based on the support set   and the initial set of frequency coefficients {circumflex over (ƒ)} 0 . 
 
     
     
       6. The method of  claim 1 , further comprising:
 determining that a norm based on a binary matrix B based on the support set   and the initial set of frequency coefficients {circumflex over (ƒ)} 0  is not less than a selected threshold; 
 obtaining a second plurality of sets of signal samples, each set comprising a plurality of samples of the signal ƒ(x); and 
 re-computing the initial set of frequency coefficients {circumflex over (ƒ)} 0  using the support set   and the second plurality of sets of signal samples. 
 
     
     
       7. The method of  claim 6 , further comprising:
 determining that a norm based on the binary matrix B and the re-computed initial set of frequency coefficients {circumflex over (ƒ)} 0  is less than or equal to the selected threshold; and 
 generating a set of frequency coefficients {circumflex over (ƒ)} using the binary matrix B and the re-computed initial set of frequency coefficients {circumflex over (ƒ)} 0 . 
 
     
     
       8. The method of  claim 1 , wherein the signal ƒ(x) is received from a signal source comprising at least one of a radar, a lidar, an antenna, a sonar, a camera, an infra-red sensor, an electro-magnetic radiation sensor, and an acoustic sensor. 
     
     
       9. A system for identifying magnitudes of frequency components of a signal ƒ(x), the system comprising:
 a first processor; and 
 a first memory in electrical communication with the first processor, the first memory comprising instructions which, when executed by a processing unit comprising at least one of the first processor and a second processor, and in electronic communication with a memory module comprising at least one of the first memory and a second memory, program the processing unit to: 
 obtain at a receiver a first plurality of sets of samples of a signal received by an antenna or a sensor, each set comprising a plurality of samples of the signal ƒ(x) obtained using a respective sampling interval based on a respective shuffling parameter, cardinality of each set being greater than an upper bound (R) of a number of non-zero frequency components of the signal ƒ(x) and less than a number of samples N of the signal ƒ(x) according to a Nyquist rate, wherein obtaining each set of signal samples comprises subsampling by the receiver the signal at a respective rate less than the Nyquist rate, and at least one set of signal samples determines a support set  ; and 
 compute an initial set of frequency coefficients {circumflex over (ƒ)} 0  using a support set   and frequency coefficients of the first plurality of sets of signal samples, the support set   identifying indices of the non-zero frequency coefficients of the signal ƒ(x). 
 
     
     
       10. The system of  claim 9 , wherein to obtain the first plurality of sets of signal samples the processing unit is configured to access from the memory module T sets of signal samples, wherein:
 T is on the order of O(1) or on the order of O(R log R  N); and 
 a t-th set of signal samples, wherein index t ranges from 1 through T, comprises P (t)  signal samples, P (t)  being greater than R and smaller than N. 
 
     
     
       11. The system of  claim 9 , wherein to obtain the first plurality of sets of signal samples the processing unit is configured to:
 determine the number of samples (N) of the signal ƒ(x) according to the Nyquist rate, and obtain the upper bound (R) of the number of non-zero frequency components of the signal; 
 select a number of sets (T), wherein T is on the order of O(1) or on the order of O(R log R  N), and select T recovery parameters P (t) , wherein index t ranges from 1 through T; 
 for each recovery parameter P (t) , configure a signal sampler to sample the signal ƒ(x) at P (t)  distinct locations, providing the first plurality of T sets of signal samples, each sample set having P (t)  samples. 
 
     
     
       12. The system of  claim 9 , wherein to compute the initial set of frequency coefficients {circumflex over (ƒ)} 0  the processing unit is programmed to:
 multiply the first plurality of sets of signal samples by: (i) a discrete Fourier transform (DFT) matrix F comprising T DFT submatrices, each submatrix having a size P (t) , and index t ranging from 1 through T, and (ii) a binary matrix B based on the support set  . 
 
     
     
       13. The system of  claim 9 , wherein the instructions further program the processing unit to:
 generate a set of frequency coefficients {circumflex over (ƒ)} using a binary matrix B based on the support set S and the initial set of frequency coefficients {circumflex over (ƒ)} 0 . 
 
     
     
       14. The system of  claim 9 , wherein the instructions further program the processing unit to:
 determine that a norm based on a binary matrix B based on the support set   and the initial set of frequency coefficients {circumflex over (ƒ)} 0  is not less than a selected threshold; 
 obtain a second plurality of sets of signal samples, each set comprising a plurality of samples of the signal ƒ(x); and 
 re-compute the initial set of frequency coefficients {circumflex over (ƒ)} 0  using the support set   and the second plurality of sets of signal samples. 
 
     
     
       15. The system of  claim 14 , wherein the instructions further program the processing unit to:
 determine that a norm based on the binary matrix B and the re-computed initial set of frequency coefficients {circumflex over (ƒ)} 0  is less than or equal to the selected threshold; and 
 generate a set of frequency coefficients {circumflex over (ƒ)} using the binary matrix B and the re-computed initial set of frequency coefficients {circumflex over (ƒ)} 0 . 
 
     
     
       16. The system of  claim 9 , wherein the signal ƒ(x) is received from a signal source comprising at least one of a radar, a lidar, an antenna, a sonar, a camera, an infra-red sensor, an electro-magnetic radiation sensor, and an acoustic sensor. 
     
     
       17. A method for identifying frequency components of a signal ƒ(x), the method comprising performing by a processor the steps of:
 (a) initially designating a current set of candidate support coefficients (   k ) as a current set of aliased support coefficients    k ; 
 (b) obtaining at a receiver a plurality of sets of samples comprising a first set of K shuffled samples of the signal ƒ(x), received by an antenna or a sensor and corresponding to a first sampling interval based on a first shuffling parameter, wherein K is a fraction of a number of samples (N) of the signal ƒ(x) according to a Nyquist rate, and wherein obtaining the first set of K shuffled samples comprises subsampling by the receiver the signal at a rate less than the Nyquist rate, at least one set of signal samples determining the set of aliased support coefficients    k ; 
 (c) filtering the shuffled samples in the first set, and computing a first plurality of frequency coefficients of the shuffled samples in the first set; and 
 (d) removing from the current set of aliased support coefficients    k  a subset of candidate support coefficients wherein, for each candidate support coefficient in the subset a value of a corresponding computed frequency coefficient in the first plurality of frequency coefficients is less than a threshold. 
 
     
     
       18. The method of  claim 17 , further comprising:
 obtaining a second set of shuffled samples of the signal ƒ(x), corresponding to a second sampling interval based on a second shuffling parameter; 
 filtering the shuffled samples in the second set, and computing a second plurality of frequency coefficients of the shuffled samples in the second set; and 
 removing from the current set of aliased support coefficients    k  a subset of candidate support coefficients wherein, for each candidate support coefficient in the subset a value of a corresponding computed frequency coefficient in the second plurality of frequency coefficients is less than the threshold. 
 
     
     
       19. The method of  claim 18 , wherein:
 the first shuffling parameter is a first coprime of an index limit (M k ) of the current set of candidate support coefficients (   k ); and 
 the second shuffling parameter is a second, different coprime of the index limit (M k ). 
 
     
     
       20. The method of  claim 17 , wherein:
 an index limit (M k ) of the current set of candidate support coefficients (   k ) is associated with a support set growth factor ρ k  that is a ratio of an index limit (M k ) and the number of samples in the first set of shuffled samples (K). 
 
     
     
       21. The method of  claim 17 , further comprising:
 obtaining a prior set of aliased support coefficients    k−1 ; and 
 dealiasing the prior set of aliased support coefficients to obtain the current set of candidate support coefficients (   k ). 
 
     
     
       22. The method of  claim 17 , further comprising:
 (e) selecting a next index limit (M k+1 ) of a next set of candidate support coefficients (   k+1 ), wherein the next index limit is greater than a current index limit (M k ) of the current set of candidate support coefficients(   k ); 
 (f) after the step (d), dealiasing the current set of aliased support coefficients (   k ) using the next index limit (M k+1 ), to obtain the next set of candidate support coefficients (   k+1 ); 
 (g) updating the current set of candidate support coefficients (   k ) by designating the next set of candidate support coefficients (   k+1 ) as the current set of candidate support coefficients ( M k ); and 
 (h) repeating the steps (a) through (d) using the updated current set of candidate support coefficients (   k ). 
 
     
     
       23. The method of  claim 22 , further comprising:
 determining that a next index limit (M k+1 ) is not less than a number of samples (N) of the signal ƒ(x) according to a Nyquist rate; and 
 after the step (h), designating the current set of aliased support coefficients    k  as a final set of aliased support coefficients  . 
 
     
     
       24. The method of  claim 17 , wherein obtaining the first set of shuffled samples of the signal ƒ(x) comprises:
 selecting the first sampling interval using the first shuffling parameter (Q k   (l) ), wherein the first shuffling parameter corresponds to an index limit (M k ) of the current set of candidate support coefficients (   k ); 
 sampling the signal ƒ(x) using the first sampling interval, to obtain a first sampled signal; and 
 shuffling the first sampled signal using the first shuffling parameter and the index limit. 
 
     
     
       25. The method of  claim 17 , wherein obtaining the first set of shuffled samples of the signal ƒ(x) comprises:
 selecting the first shuffling parameter (Q k   (l) ) corresponding to an index limit (M k ) of the current set of candidate support coefficients (   k ); and 
 accessing from memory the first set of shuffled samples corresponding to the first shuffling parameter. 
 
     
     
       26. The method of  claim 17 , wherein filtering the shuffled samples in the first set comprises filtering the first set using a Gaussian filter having a standard deviation (σ) that is based on an upper bound of a number of non-zero frequency components (R) of the signal ƒ(x), to obtain a filtered shuffled signal. 
     
     
       27. The method of  claim 17 , further comprising generating the current set of candidate support coefficients by:
 selecting a first index limit (M 1 ), wherein M 1  is less than the number of samples (N) of the signal ƒ(x) according to the Nyquist rate; 
 obtaining a plurality of samples of the signal ƒ(x); 
 determining M 1  frequency coefficients of a signal comprising the plurality of samples; and 
 including each non-zero frequency coefficient from the M 1  frequency coefficients as a respective candidate support coefficient in the current set of candidate support coefficients. 
 
     
     
       28. The method of  claim 27 , wherein:
 a non-zero frequency coefficient comprises a frequency coefficient having a magnitude greater than a specified threshold value; and 
 a frequency coefficient designated as a zero coefficient has a magnitude less than or equal to the specified threshold value. 
 
     
     
       29. A system for identifying frequency components of a signal ƒ(x), the system comprising:
 a first processor; and 
 a first memory in electrical communication with the first processor, the first memory comprising instructions which, when executed by a processing unit comprising at least one of the first processor and a second processor, and in electronic communication with a memory module comprising at least one of the first memory and a second memory, program the processing unit to: 
 (a) initially designate a current set of candidate support coefficients (   k ) as a current set of aliased support coefficients    k ; 
 (b) obtain a plurality of sets of samples comprising a first set of K shuffled samples of the signal ƒ(x), received by an antenna or a sensor and corresponding to a first sampling interval based on a first shuffling parameter, wherein K is a fraction of a number of samples (N) of the signal ƒ(x) according to a Nyquist rate, wherein obtaining the first set of K shuffled samples comprises subsampling by the receiver the signal at a rate less than the Nyquist rate, at least one set of signal samples determining the set of aliased support coefficients    k ; 
 (c) filter the shuffled samples in the first set, and computing a first plurality of frequency coefficients of the shuffled samples in the first set; and 
 (d) remove from the current set of aliased support coefficients    k  a subset of candidate support coefficients wherein, for each candidate support coefficient in the subset a value of a corresponding computed frequency coefficient in the first plurality of frequency coefficients is less than a threshold. 
 
     
     
       30. The system of  claim 29 , wherein the processing unit is further programmed to:
 obtain a second set of shuffled samples of the signal ƒ(x), corresponding to a second sampling interval based on a second shuffling parameter; 
 filter the shuffled samples in the second set, and computing a second plurality of frequency coefficients of the shuffled samples in the second set; and 
 remove from the current set of aliased support coefficients    k  a subset of candidate support coefficients wherein, for each candidate support coefficient in the subset a value of a corresponding computed frequency coefficient in the second plurality of frequency coefficients is less than the threshold. 
 
     
     
       31. The system of  claim 30 , wherein:
 the first shuffling parameter is a first coprime of an index limit (M k ) of the current set of candidate support coefficients (   k ); and 
 the second shuffling parameter is a second, different coprime of the index limit (M k ). 
 
     
     
       32. The system of  claim 29 , wherein:
 an index limit (M k ) of the current set of candidate support coefficients (   k ) is associated with a support set growth factor ρ k  that is a ratio of an index limit (M k ) and the number of samples in the first set of shuffled samples (K). 
 
     
     
       33. The system of  claim 29 , wherein the processing unit is further programmed to:
 obtain a prior set of aliased support coefficients    k−1 ; and 
 dealias the prior set of aliased support coefficients to obtain the current set of candidate support coefficients (   k ). 
 
     
     
       34. The system of  claim 29 , wherein the processing unit is further programmed to:
 (e) select a next index limit (M k+1 ) of a next set of candidate support coefficients (   k+1 ), wherein the next index limit is greater than a current index limit (M k ) of the current set of candidate support coefficients (   k ); 
 (f) after performing the operation (d), dealias the current set of aliased support coefficients (   k ) using the next index limit (M k+1 ), to obtain the next set of candidate support coefficients (   k+1 ); 
 (g) update the current set of candidate support coefficients (   k ) by designating the next set of candidate support coefficients (   k+1 ) as the current set of candidate support coefficients (   k ); and 
 (h) repeat the operations (a) through (d) using the updated current set of candidate support coefficients (   k ). 
 
     
     
       35. The system of  claim 34 , wherein the processing unit is further programmed to:
 determine that a next index limit (M k+1 ) is not less than a number of samples (N) of the signal ƒ(x) according to a Nyquist rate; and 
 after the operation (h), designate the current set of aliased support coefficients    k  as a final set of aliased support coefficients  . 
 
     
     
       36. The system of  claim 29 , wherein to obtain the first set of shuffled samples of the signal ƒ(x) the processing unit is programmed to:
 select the first sampling interval using the first shuffling parameter (Q k   (l) ), wherein the first shuffling parameter corresponds to an index limit (M k ) of the current set of candidate support coefficients (   k ); 
 configure a signal sampler to sample the signal ƒ(x) using the first sampling interval, to obtain a first sampled signal; and 
 shuffle the first sampled signal using the first shuffling parameter and the index limit. 
 
     
     
       37. The system of  claim 29 , wherein to obtain the first set of shuffled samples of the signal ƒ(x) the processing unit is programmed to:
 select the first shuffling parameter (Q k   (l) ) corresponding to an index limit (M k ) of the current set of candidate support coefficients (   k ); and 
 access from the memory module the first set of shuffled samples corresponding to the first shuffling parameter. 
 
     
     
       38. The system of  claim 29 , wherein to filter the shuffled samples in the first set the processing unit is programmed to filter the first set using a Gaussian function having a standard deviation (σ) that is based on an upper bound of a number of non-zero frequency components (R) of the signal ƒ(x), to obtain a filtered shuffled signal. 
     
     
       39. The system of  claim 29 , wherein the processing unit is further programmed to generate the current set of candidate support coefficients by:
 selecting a first index limit (M 1 ), wherein M 1  is less than the number of samples (N) of the signal ƒ(x) according to the Nyquist rate; 
 obtaining a plurality of samples of the signal ƒ(x); 
 determining M 1  frequency coefficients of a signal comprising the plurality of samples; and 
 including each non-zero frequency coefficient from the M 1  frequency coefficients as a respective candidate support coefficient in the current set of candidate support coefficients. 
 
     
     
       40. The system of  claim 39 , wherein:
 a non-zero frequency coefficient comprises a frequency coefficient having a magnitude greater than a specified threshold value; and 
 a frequency coefficient designated as a zero coefficient has a magnitude less than or equal to the specified threshold value. 
 
     
     
       41. A method for generating non-zero frequency coefficients of a signal ƒ(x), the method comprising performing by a processor the steps of:
 obtaining at a receiver a plurality of sets of samples of the signal ƒ(x) received by an antenna or a sensor and comprising a first set corresponding to a first sampling interval and a different second set, wherein obtaining each of the sets of samples comprises subsampling by the receiver the signal at a rate less than a Nyquist rate corresponding to the signal; 
 determining indices of the non-zero frequency coefficients of the signal ƒ(x) using at least the first set, the first sampling interval corresponding to the indices of non-zero frequency coefficients; and 
 determining values of the non-zero frequency coefficients of the signal ƒ(x) using the indices thereof and at least the second set. 
 
     
     
       42. The method of  claim 41 , wherein determining the indices of the non-zero frequency coefficients comprises:
 obtaining: (i) a number of samples (N) of the signal ƒ(x) according to a Nyquist rate, and (ii) an upper bound of a number of non-zero frequency components (R) of the signal ƒ(x); 
 selecting a sample size K, a number of iterations P, a plurality of support set growth factors ρ k , and a plurality of index limits M k , each index limit representing an index limit of a respective set of candidate support coefficients    k , wherein M k =ρ k K and 
 
       
         
           
             
               
                 N 
                 = 
                 
                   K 
                   ⁢ 
                   
                     
                       ∏ 
                       
                         k 
                         = 
                         1 
                       
                       P 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       ρ 
                       k 
                     
                   
                 
               
               ; 
             
           
         
       
       and
 determining a current set of aliased support coefficients    k  using the first set of samples of the signal ƒ(x), the first set comprising less than N samples. 
 
     
     
       43. The method of  claim 41 , wherein determining the indices of the non-zero frequency coefficients comprises:
 performing at least one iteration, comprising:
 obtaining a current set of candidate support coefficients    k  by dealiasing the current set of aliased support coefficients    k ; 
 determining a next set of aliased support coefficients using the current set of candidate support coefficients    k  and at least one set of samples from the plurality of sets of samples of the signal ƒ(x), each one of the at least one set of samples being obtained using a sampling interval based on M k ; and 
 designating the next set of aliased support coefficients as the current set of aliased support coefficients    k . 
 
 
     
     
       44. The method of  claim 41 , wherein determining the indices of the non-zero frequency coefficients comprises:
 performing at least one iteration, comprising:
 obtaining a current set of candidate support coefficients    k  by dealiasing the current set of aliased support coefficients    k ; 
 determining a next set of aliased support coefficients using the current set of candidate support coefficients    k  and at least one set of samples from the plurality of sets of samples of the signal ƒ(x), each one of the at least one set of samples being obtained using a sampling interval based on M k ; and 
 designating the next set of aliased support coefficients as final set of aliased support coefficients S, the final set of aliased support coefficients representing the indices of the non-zero frequency coefficients. 
 
 
     
     
       45. The method of  claim 41 , wherein the signal ƒ(x) comprises a one-dimensional signal obtained from a signal source comprising at least one of a radar, a lidar, an antenna, a sonar, a camera, an infra-red sensor, an electro-magnetic radiation sensor, and an acoustic sensor. 
     
     
       46. The method of  claim 41 , further comprising:
 mapping a multi-dimensional signal y(x) into a one-dimensional signal ƒ(x); and 
 storing an inverse mapping identifying a sample index for y(x) corresponding to a sample index for ƒ(x), 
 wherein obtaining the plurality of sets of samples of the signal ƒ(x) comprises:
 selecting a plurality of sample indices of ƒ(x); and 
 obtaining samples of y(x) at a plurality of sample indices of y(x), each one being determined via the inverse mapping and a respective selected sample index of ƒ(x). 
 
 
     
     
       47. The method of  claim 46 , wherein the non-zero frequency coefficients of the signal ƒ(x) represent non-zero frequency coefficients of the multi-dimensional signal y(x). 
     
     
       48. The method of  claim 46 , wherein the multi-dimensional signal y(x) comprises a multi-dimensional signal obtained from a signal source comprising at least one of a radar, a lidar, an antenna, a sonar, a camera, an infra-red sensor, an electro-magnetic radiation sensor, and an acoustic sensor. 
     
     
       49. The method of  claim 41 , wherein:
 a non-zero frequency coefficient comprises a frequency coefficient having a magnitude greater than a specified threshold value; and 
 a frequency coefficient designated as a zero coefficient has a magnitude less than or equal to the specified threshold value. 
 
     
     
       50. The method of  claim 41 , wherein:
 the step of determining indices of the non-zero frequency coefficients is performed using a first value (N 1 ) of a number of samples of the signal ƒ(x) according to a Nyquist rate, to obtain a first support set    1 ; 
 the step of determining indices of the non-zero frequency coefficients is repeated using a second value (N 2 ) of the number of samples, to obtain a second support set    2 ,
 the method further comprising: 
 generating a final support set as a union of the first and second support sets; and 
 designating coefficients of the final support set as the indices of the non-zero frequency coefficients. 
 
 
     
     
       51. A system for generating non-zero frequency coefficients of a signal ƒ(x), the system comprising:
 a first processor; and 
 a first memory in electrical communication with the first processor, the first memory comprising instructions which, when executed by a processing unit comprising at least one of the first processor and a second processor, and in electronic communication with a memory module comprising at least one of the first memory and a second memory, program the processing unit to: 
 obtain at a receiver a plurality of sets of samples of the signal ƒ(x) received by an antenna or a sensor and comprising a first set corresponding to a first sampling interval and a different second set, wherein obtaining each of the sets of samples comprises subsampling by the receiver the signal at a rate less than a Nyquist rate corresponding to the signal; 
 determine indices of the non-zero frequency coefficients of the signal ƒ(x) using at least the first set, the first sampling interval corresponding to the indices of non-zero frequency coefficients; and 
 determine values of the non-zero frequency coefficients of the signal ƒ(x) using the indices thereof and at least the second set. 
 
     
     
       52. The system of  claim 51 , wherein to determine the indices of the non-zero frequency coefficients the processing unit is programmed to:
 obtain: (i) a number of samples (N) of the signal ƒ(x) according to a Nyquist rate, and (ii) an upper bound of a number of non-zero frequency components (R) of the signal ƒ(x); 
 select a sample size K, a number of iterations P, a plurality of support set growth factors ρ k , and a plurality of index limits M k , each index limit representing an index limit of a respective set of candidate support coefficients    k , wherein M k =ρ k K and 
 
       
         
           
             
               
                 N 
                 = 
                 
                   K 
                   ⁢ 
                   
                     
                       ∏ 
                       
                         k 
                         = 
                         1 
                       
                       P 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       ρ 
                       k 
                     
                   
                 
               
               ; 
             
           
         
       
       and
 determine a current set of aliased support coefficients    k  using the first set of samples of the signal ƒ(x), the first set comprising less than N samples. 
 
     
     
       53. The system of  claim 51 , wherein to determine the indices of the non-zero frequency coefficients the processing unit is programmed to:
 perform at least one iteration, comprising:
 obtaining a current set of candidate support coefficients    k  by dealiasing the current set of aliased support coefficients    k ; 
 
 determining a next set of aliased support coefficients using the current set of candidate support coefficients    k  and at least one set of samples from the plurality of sets of samples of the signal ƒ(x), each one of the at least one set of samples being obtained using a sampling interval based on M k ; and 
 designating the next set of aliased support coefficients as the current set of aliased support coefficients    k . 
 
     
     
       54. The system of  claim 51 , wherein to determine the indices of the non-zero frequency coefficients the processing unit is programmed to:
 perform at least one iteration, comprising:
 obtaining a current set of candidate support coefficients    k  by dealiasing the current set of aliased support coefficients    k ; 
 determining a next set of aliased support coefficients using the current set of candidate support coefficients    k  and at least one set of samples from the plurality of sets of samples of the signal ƒ(x), each one of the at least one set of samples being obtained using a sampling interval based on M k ; and 
 designating the next set of aliased support coefficients as final set of aliased support coefficients  , the final set of aliased support coefficients representing the indices of the non-zero frequency coefficients. 
 
 
     
     
       55. The system of  claim 51 , wherein the signal ƒ(x) comprises a one-dimensional signal obtained from a signal source comprising at least one of a radar, a lidar, an antenna, a sonar, a camera, an infra-red sensor, an electro-magnetic radiation sensor, and an acoustic sensor. 
     
     
       56. The system of  claim 51 , wherein the processing unit is further programmed to:
 map a multi-dimensional signal y(x) into a one-dimensional signal ƒ(x); and 
 store an inverse mapping identifying a sample index for y(x) corresponding to a sample index for ƒ(x), 
 wherein to obtain the plurality of sets of samples of the signal ƒ(x) the processing unit is programmed to:
 select a plurality of sample indices of ƒ(x); and 
 obtain samples of y(x) at a plurality of sample indices of y(x), each one being determined via the inverse mapping and a respective selected sample index of ƒ(x). 
 
 
     
     
       57. The system of  claim 56 , wherein the non-zero frequency coefficients of the signal ƒ(x) represent non-zero frequency coefficients of the multi-dimensional signal y(x). 
     
     
       58. The system of  claim 56 , wherein the multi-dimensional signal y(x) comprises a multi-dimensional signal obtained from a signal source comprising at least one of a radar, a lidar, an antenna, a sonar, a camera, an infra-red sensor, an electro-magnetic radiation sensor, and an acoustic sensor. 
     
     
       59. The system of  claim 51 , wherein:
 a non-zero frequency coefficient comprises a frequency coefficient having a magnitude greater than a specified threshold value; and 
 a frequency coefficient designated as a zero coefficient has a magnitude less than or equal to the specified threshold value. 
 
     
     
       60. The system of  claim 51 , wherein the processing unit is programmed to:
 determine the indices of the non-zero frequency coefficients using a first value (N 1 ) of a number of samples of the signal ƒ(x) according to a Nyquist rate, to obtain a first support set    1 ; 
 determine the indices of the non-zero frequency coefficients again, using a second value (N 2 ) of the number of samples, to obtain a second support set    2 ; 
 generate a final support set as a union of the first and second support sets; and 
 designate coefficients of the final support set as the indices of the non-zero frequency coefficients.