research-article

Nested Periodic Matrices and Dictionaries: New Signal Representations for Period Estimation

Authors:

Srikanth V. Tenneti,

P. P. VaidyanathanAuthors Info & Claims

IEEE Transactions on Signal Processing, Volume 63, Issue 14

Pages 3736 - 3750

https://doi.org/10.1109/TSP.2015.2434318

Published: 01 July 2015 Publication History

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<sub>2</sub> 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<sub>1</sub> norm minimization techniques, we can incorporate a number of new and computationally simple dictionaries.

References

[1]

W. R. Atchley, J. Zhao, A. D. Fernandes, and T. Drüke, “Solving the protein sequence metric problem,” in Proc. Nat. Acad. Sci., USA, 2005, vol. 102, pp. 6395–6400.

[2]

D. D. Muresan and T. W. Parks, “Orthogonal, exactly periodic subspace decomposition,” IEEE Trans. Signal Process., vol. 51, no. 9, pp. 2270–2279, Sep. 2003.

Digital Library

[3]

D. L. Donoho and M. Elad, “Optimally sparse representation in general (nonorthogonal) dictionaries via L1 minimization,” in Proc. Nat. Acad. Sci., vol. 100, no. 5, pp. 2197–2202, 2003.

[4]

E. J. Candes and T. Tao, “Decoding by linear programming,” IEEE Trans. Inf. Theory, vol. 51, no. 12, pp. 4203–4215, Dec. 2005.

Digital Library

[5]

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Oxford, U.K.: Oxford Univ. Press, 2008.

[6]

J. A. Tropp, “Greed is good: Algorithmic results for sparse approximation,” IEEE Trans. Inf. Theory, vol. 50, pp. 2231–2242, Oct. 2004.

Digital Library

[7]

L. Marsella, F. Sirocco, A. Trovato, F. Seno, and S. C. E. Tosatto, “REPETITA: Detection and discrimination of the periodicity of protein solenoid repeats by discrete Fourier Transform,” in Bioinformatics, vol. 25, no. 12, pp. i289–i295, 2009.

Digital Library

[8]

T. S. Lugovaya, Biometric human identification based on electrocardiogram, Master's thesis, Faculty of Comput. Technol. Informatics, Electrotech. Univ. “LETI”, Saint-Petersburg, Russian Fed.: 2005.

[9]

A. L. Goldberger, L. A. N. Amaral, L. Glass, J. M. Hausdorff, P. C. Ivanov, R. G. Mark et al., “PhysioBank, PhysioToolkit, and PhysioNet: Components of a new research resource for complex physiologic signals,” in Circulation, vol. 101, no. 23, pp. e215–e220, Jun. 2000.

[10]

M. F. Duarte and R. G. Baraniuk, “Spectral compressive sensing,” in Appl. Comp. Harmon. Anal., vol. 35, no. 1, pp. 111–129, Jul. 2013.

[11]

M. A. Andrade, C. Perez-Iratxeta, and C. P. Ponting, “Protein repeats: Structures, functions, and evolution,” in J. Structur. Biol., vol. 134, pp. 117–131, 2001.

[12]

M. J. Wainwright, “Sharp thresholds for high dimensional and noisy sparsity recovery using l1 constrained quadratic programming (Lasso),” IEEE Trans. Inf. Theory, vol. 55, no. 5, pp. 2183–2202, May 2009.

Digital Library

[13]

M. Planat, “Ramanujan sums for signal processing of low frequency noise,” in Proc. IEEE Intl. Freq. Control Symp. PDA Exhibit., 2002, pp. 715–720.

[14]

M. Planat, M. Minarovjech, and M. Saniga, “Ramanujan sums analysis of long-periodic sequenes and $1= {\rm f}$ noise,” in EPL J., vol. 85, pp. 40005:1–5, 2009.

[15]

N. Sloane, A library of Hadamard matrices, [Online]. Available: http://neilsloane.com/hadamard/.

[16]

P. Stoica and R. Moses, Spectral Analysis of Signals, Englewood Cliffs, NJ USA: Prentice-Hall, 2005.

[17]

P. P. Vaidyanathan, Multirate Systems and Filter Banks, Englewood Cliffs, NJ USA: Prentice-Hall, 1993.

Digital Library

[18]

P. P. Vaidyanathan, “Ramanujan sums in the context of signal processing: Part I: Fundamentals,” IEEE Trans. Signal Process., vol. 62, no. 16, pp. 4145–4157, Aug. 2014.

[19]

P. P. Vaidyanathan, “Ramanujan sums in the context of signal processing: Part II: FIR representations and applications,” IEEE Trans. Signal Process., vol. 62, no. 16, pp. 4158–4172, Aug. 2014.

[20]

P. P. Vaidyanathan, “Ramanujan-sum expansions for finite duration (FIR) sequences,” in IEEE Int. Conf. Acoust., Speech, Signal Process., Florence, Italy, 2014.

[21]

P. P. Vaidyanathan and P. Pal, “The Farey dictionary for sparse representation of periodic signals,” in IEEE Int. Conf. Acoust., Speech, Signal Process, Florence, Italy, 2014.

[22]

R. G. Baraniuk, “Compressive sensing,” IEEE Signal Process. Mag., vol. 24, no. 4, pp. 118–124, Jul. 2007.

[23]

R. O. Schmidt, “Multiple emitter location and signal parameter estimation,” in Proc. RADC, Spectral Estimation Workshop 1979, Rome, NY USA, pp. 243–258.

[24]

S. Ramanujan, “On certain trigonometrical sums and their applications in the theory of numbers,” in Trans. Cambridge Philosoph. Soc., vol. XXII, no. 13, pp. 259–276, 1918.

[25]

S.-C. Pei and K.-S. Lu, “Intrinsic integer-periodic functions for discrete periodicity detection,” IEEE Signal Process. Lett., vol. 22, no. 8, pp. 1108–1112, Aug. 2015.

[26]

T. Aittokallio, M. Gyllenberg, O. Nevalainen, and O. Polo, “Testing for periodicity in signals: An application to detect partial upper airway obstruction during sleep,” in J. Theoretic. Med., vol. 3, pp. 231–245.

[27]

T. Ritte, Walsh Hadamard transforms: A literature survey, [Online]. Available: http://www.ciphersbyritter.com/RES/WALHAD.HTM.

[28]

W. A. Sethares and T. W. Staley, “Periodicity transforms,” IEEE Trans. Signal Process., vol. 47, pp. 2953–2964, Nov. 1999.

Digital Library

Cited By

Ma BMcNeil MMagner ABogdanov PBaeza-Yates RBonchi F(2024)Low Rank Multi-Dictionary Selection at ScaleProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671723(2106-2117)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671723
Colominas MWu H(2023)An Iterative Warping and Clustering Algorithm to Estimate Multiple Wave-Shape Functions From a Nonstationary Oscillatory SignalIEEE Transactions on Signal Processing10.1109/TSP.2023.325288371(701-712)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1109/TSP.2023.3252883
Kulkarni PVaidyanathan P(2023)Periodicity-Aware Signal Denoising Using Capon-Optimized Ramanujan Filter Banks and Pruned Ramanujan DictionariesIEEE Transactions on Signal Processing10.1109/TSP.2023.324410971(494-511)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1109/TSP.2023.3244109
Show More Cited By

Index Terms

Nested Periodic Matrices and Dictionaries: New Signal Representations for Period Estimation
1. Hardware
2. Theory of computation

Index terms have been assigned to the content through auto-classification.

Recommendations

Sparse Recovery Guarantees of Periodic Signals with Nested Periodic Dictionaries
2021 IEEE Information Theory Workshop (ITW)
Periodic signals admit sparse representations in nested periodic dictionaries (NPDs). While sparse recovery algorithms rooted in the theory of compressive sensing can successfully recover their underlying periods, existing recovery conditions derived for ...
A Sparse Decomposition Method for Periodic Signal Mixtures

This study proposes a method to decompose a signal into a set of periodic signals. The proposed decomposition method imposes a penalty on the resultant periodic subsignals in order to improve the sparsity of decomposition and avoid the overestimation of ...
Signal Space CoSaMP for Sparse Recovery With Redundant Dictionaries

Compressive sensing (CS) has recently emerged as a powerful framework for acquiring sparse signals. The bulk of the CS literature has focused on the case where the acquired signal has a sparse or compressible representation in an orthonormal basis. In ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Signal Processing

IEEE Transactions on Signal Processing Volume 63, Issue 14

July15, 2015

276 pages

ISSN:1053-587X

Issue’s Table of Contents

Copyright © 2015.

Publisher

IEEE Press

Publication History

Published: 01 July 2015

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ma BMcNeil MMagner ABogdanov PBaeza-Yates RBonchi F(2024)Low Rank Multi-Dictionary Selection at ScaleProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671723(2106-2117)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671723
Colominas MWu H(2023)An Iterative Warping and Clustering Algorithm to Estimate Multiple Wave-Shape Functions From a Nonstationary Oscillatory SignalIEEE Transactions on Signal Processing10.1109/TSP.2023.325288371(701-712)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1109/TSP.2023.3252883
Kulkarni PVaidyanathan P(2023)Periodicity-Aware Signal Denoising Using Capon-Optimized Ramanujan Filter Banks and Pruned Ramanujan DictionariesIEEE Transactions on Signal Processing10.1109/TSP.2023.324410971(494-511)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1109/TSP.2023.3244109
Das AMajumder CDe DRaha ANaskar M(2023)HIPED_AP: Energy-Efficient Hardware Accelerators for Hidden Periodicity DetectionIEEE Transactions on Computers10.1109/TC.2023.327056872:10(2781-2794)Online publication date: 3-May-2023
https://dl.acm.org/doi/10.1109/TC.2023.3270568
Wen QHe KSun LZhang YKe MXu HLi GLi ZIdreos SSrivastava D(2021)RobustPeriod: Robust Time-Frequency Mining for Multiple Periodicity DetectionProceedings of the 2021 International Conference on Management of Data10.1145/3448016.3452779(2328-2337)Online publication date: 9-Jun-2021
https://dl.acm.org/doi/10.1145/3448016.3452779
McNeil MZhang LBogdanov PZhu FChin Ooi BMiao CWang HSkrypnyk IHsu WChawla S(2021)Temporal Graph Signal DecompositionProceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining10.1145/3447548.3467379(1191-1201)Online publication date: 14-Aug-2021
https://dl.acm.org/doi/10.1145/3447548.3467379
Saidi PAtia G(2021)Sparse Recovery Guarantees of Periodic Signals with Nested Periodic Dictionaries2021 IEEE Information Theory Workshop (ITW)10.1109/ITW48936.2021.9611507(1-6)Online publication date: 17-Oct-2021
https://dl.acm.org/doi/10.1109/ITW48936.2021.9611507
Zhang LZhang WMcNeil MChengwang NMatteson DBogdanov P(2021)AURORA: A Unified fRamework fOR Anomaly detection on multivariate time seriesData Mining and Knowledge Discovery10.1007/s10618-021-00771-735:5(1882-1905)Online publication date: 1-Sep-2021
https://dl.acm.org/doi/10.1007/s10618-021-00771-7
Shah SChakka VReddy A(2020)Orthogonal and Non-Orthogonal Signal Representations Using New Transformation Matrices Having NPM StructureIEEE Transactions on Signal Processing10.1109/TSP.2020.297193668(1229-1242)Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.1109/TSP.2020.2971936
Tenneti SVaidyanathan P(2019)iMUSIC: A Family of MUSIC-Like Algorithms for Integer Period EstimationIEEE Transactions on Signal Processing10.1109/TSP.2018.287903967:2(367-382)Online publication date: 15-Jan-2019
https://dl.acm.org/doi/10.1109/TSP.2018.2879039
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents