Nested Periodic Matrices and Dictionaries: New Signal Representations for Period Estimation
Authors:
- 18 May 2015
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 63 (14) , 3736-3750
Abstract
In this paper, we propose a new class of techniques to identify periodicities in data. We target the period estimation directly rather than inferring the period from the signal's spectrum. By doing so, we obtain several advantages over the traditional spectrum estimation techniques such as DFT and MUSIC. Apart from estimating the unknown period of a signal, we search for finer periodic structure within the given signal. For instance, it might be possible that the given periodic signal was actually a sum of signals with much smaller periods. For example, adding signals with periods 3, 7, and 11 can give rise to a period 231 signal. We propose methods to identify these “hidden periods” 3, 7, and 11. We first propose a new family of square matrices called Nested Periodic Matrices (NPMs), having several useful properties in the context of periodicity. These include the DFT, Walsh-Hadamard, and Ramanujan periodicity transform matrices as examples. Based on these matrices, we develop high dimensional dictionary representations for periodic signals. Various optimization problems can be formulated to identify the periods of signals from such representations. We propose an approach based on finding the least l 2 norm solution to an under-determined linear system. Alternatively, the period identification problem can also be formulated as a sparse vector recovery problem and we show that by a slight modification to the usual l 1 norm minimization techniques, we can incorporate a number of new and computationally simple dictionaries.Keywords
Funding Information
- Information Science and Technology IST initiative of Caltech
This publication has 21 references indexed in Scilit:
- Ramanujan Sums in the Context of Signal Processing—Part II: FIR Representations and ApplicationsIEEE Transactions on Signal Processing, 2014
- Ramanujan Sums in the Context of Signal Processing—Part I: FundamentalsIEEE Transactions on Signal Processing, 2014
- Spectral compressive sensingApplied and Computational Harmonic Analysis, 2013
- Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$-Constrained Quadratic Programming (Lasso)IEEE Transactions on Information Theory, 2009
- Decoding by Linear ProgrammingIEEE Transactions on Information Theory, 2005
- Greed is Good: Algorithmic Results for Sparse ApproximationIEEE Transactions on Information Theory, 2004
- Ramanujan sums for signal processing of low frequency noise2003
- Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ 1 minimizationProceedings of the National Academy of Sciences, 2003
- Protein Repeats: Structures, Functions, and EvolutionJournal of Structural Biology, 2001
- Periodicity transformsIEEE Transactions on Signal Processing, 1999