Citation
Tenneti, Srikanth Venkata (2018) The Nested Periodic Subspaces: Extensions of Ramanujan Sums for Period Estimation. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/1n4t5876. http://resolver.caltech.edu/CaltechTHESIS:06062018132643508
Abstract
In the year 1918, the Indian mathematician Srinivasa Ramanujan proposed a set of sequences called Ramanujan Sums as bases to expand arithmetic functions in number theory. Today, exactly a 100 years later, we will show that these sequences reemerge as exciting tools in a completely different context: For the extraction of periodic patterns in data. Combined with the stateoftheart techniques of DSP, Ramanujan Sums can be used as the starting point for developing powerful algorithms for periodicity applications.
The primary inspiration for this thesis comes from a recent extension of Ramanujan sums to subspaces known as the Ramanujan subspaces. These subspaces were designed to span any sequence with integer periodicity, and have many interesting properties. Starting with Ramanujan subspaces, this thesis first develops an entire family of such subspace representations for periodic sequences. This family, called Nested Periodic Subspaces due to their unique structure, turns out to be the least redundant sets of subspaces that can span periodic sequences.
Three classes of new algorithms are proposed using the Nested Periodic Subspaces: dictionaries, filter banks, and eigenspace methods based on the autocorrelation matrix of the signal. It will be shown that these methods are especially advantageous to use when the datalength is short, or when the signal is a mixture of multiple hidden periods. The dictionary techniques were inspired by recent advances in sparsity based compressed sensing. Apart from the l_{1} norm based convex programs currently used in other applications, our dictionaries can admit l_{2} norm formulations that have linear and closed form solutions, even when the systems is underdetermined. A new filter bank is also proposed using the Ramanujan sums. This, named the Ramanujan Filter Bank, can accurately track the instantaneous period for signals that exhibit time varying periodic nature. The filters in the Ramanujan Filter Bank have simple integer valued coefficients, and directly tile the period vs time plane, unlike classical STFT (Short Time Fourier Transform) and wavelets, which tile the timefrequency plane. The third family of techniques developed here are a generalization of the classic MUSIC (MUltiple SIgnal Classification) algorithm for periodic signals. MUSIC is one of the most popular techniques today for line spectral estimation. However, periodic signals are not just any unstructured line spectral signals. There is a nice harmonic spacing between the lines which is not exploited by plain MUSIC. We will show that one can design much more accurate adaptations of MUSIC using Nested Periodic Subspaces. Compared to prior variants of MUSIC for the periodicity problem, our approach is much faster and yields much more accurate results for signals with integer periods. This work is also the first extension of MUSIC that uses simple integer valued basis vectors instead of using traditional complexexponentials to span the signal subspace. The advantages of the new methods are demonstrated both on simulations, as well as real world applications such as DNA microsatellites, protein repeats and absence seizures.
Apart from practical contributions, the theory of Nested Periodic Subspaces offers answers to a number of fundamental questions that were previously unanswered. For example, what is the minimum contiguous datalength needed to be able to identify the period of a signal unambiguously? Notice that the answer we seek is a fundamental identifiability bound independent of any particular period estimation technique. Surprisingly, this basic question has never been answered before. In this thesis, we will derive precise expressions for the minimum necessary and sufficient datalengths for this question. We also extend these bounds to the context of mixtures of periodic signals. Once again, even though mixtures of periodic signals often occur in many applications, aspects such as the unique identifiability of the component periods were never rigorously analyzed before. We will present such an analysis as well.
While the above question deals with the minimum contiguous datalength required for period estimation, one may ask a slightly different question: If we are allowed to pick the samples of a signal in a noncontiguous fashion, how should we pick them so that we can estimate the period using the least number of samples? This question will be shown to be quite difficult to answer in general. In this thesis, we analyze a smaller case in this regard, namely, that of resolving between two periods. It will be shown that the analysis is quite involved even in this case, and the optimal sampling pattern takes an interesting form of sparsely located bunches. This result can also be extended to the case of multidimensional periodic signals.
We very briefly address multidimensional periodicity in this thesis. Most prior DSP literature on multidimensional discrete time periodic signals assumes the period to be parallelepipeds. But as shown by the artist M. C. Escher, one can tile the space using a much more diverse variety of shapes. Is it always possible to account for such other periodic shapes using the traditional notion of parallelepiped periods? An interesting analysis in this regard is presented towards the end of the thesis.
Item Type:  Thesis (Dissertation (Ph.D.))  

Subject Keywords:  Ramanujan Sums, Period Estimation, Nested Periodic Subspaces, Minumum Datalength  
Degree Grantor:  California Institute of Technology  
Division:  Engineering and Applied Science  
Major Option:  Electrical Engineering  
Thesis Availability:  Public (worldwide access)  
Research Advisor(s): 
 
Group:  Caltech Digital Signal Processing Group  
Thesis Committee: 
 
Defense Date:  1 June 2018  
NonCaltech Author Email:  srikutv (AT) gmail.com  
Record Number:  CaltechTHESIS:06062018132643508  
Persistent URL:  http://resolver.caltech.edu/CaltechTHESIS:06062018132643508  
DOI:  10.7907/1n4t5876  
Related URLs: 
 
ORCID: 
 
Default Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided.  
ID Code:  11029  
Collection:  CaltechTHESIS  
Deposited By:  Srikanth Venkata Tenneti  
Deposited On:  08 Jun 2018 20:35  
Last Modified:  18 Jun 2018 16:43 
Thesis Files

PDF
 Final Version
See Usage Policy. 13Mb 
Repository Staff Only: item control page