Leastsquares spectral analysis
Part of a series on 
Regression analysis 

Models 
Estimation 
Background 

Leastsquares spectral analysis (LSSA) is a method of estimating a frequency spectrum, based on a least squares fit of sinusoids to data samples, similar to Fourier analysis.^{[1]}^{[2]} Fourier analysis, the most used spectral method in science, generally boosts longperiodic noise in long gapped records; LSSA mitigates such problems.^{[3]} Unlike with Fourier analysis, data need not be equally spaced to use LSSA.
LSSA is also known as the Vaníček method^{[4]} or the GaussVaniček method^{[5]} after Petr Vaníček, and as the Lomb method^{[3]} or the Lomb–Scargle periodogram,^{[2]}^{[6]} based on the contributions of Nicholas R. Lomb^{[7]} and, independently, Jeffrey D. Scargle.^{[8]}
Historical background
The close connections between Fourier analysis, the periodogram, and leastsquares fitting of sinusoids have long been known.^{[9]} Most developments, however, are restricted to complete data sets of equally spaced samples. In 1963, Freek J. M. Barning of Mathematisch Centrum, Amsterdam, handled unequally spaced data by similar techniques,^{[10]} including both a periodogram analysis equivalent to what is now referred to the Lomb method, and leastsquares fitting of selected frequencies of sinusoids determined from such periodograms, connected by a procedure that is now known as matching pursuit with postbackfitting^{[11]} or orthogonal matching pursuit.^{[12]}
Petr Vaníček, a Canadian geodesist of the University of New Brunswick, also proposed the matchingpursuit approach, which he called "successive spectral analysis" and the result a "leastsquares periodogram", with equally and unequally spaced data, in 1969.^{[13]} He generalized this method to account for systematic components beyond a simple mean, such as a "predicted linear (quadratic, exponential, ...) secular trend of unknown magnitude", and applied it to a variety of samples, in 1971.^{[14]}
The Vaníček method was then simplified in 1976 by Nicholas R. Lomb of the University of Sydney, who pointed out its close connection to periodogram analysis.^{[7]} The definition of a periodogram of unequally spaced data was subsequently further modified and analyzed by Jeffrey D. Scargle of NASA Ames Research Center,^{[8]} who showed that with minor changes it could be made identical to Lomb's leastsquares formula for fitting individual sinusoid frequencies.
Scargle states that his paper "does not introduce a new detection technique, but instead studies the reliability and efficiency of detection with the most commonly used technique, the periodogram, in the case where the observation times are unevenly spaced," and further points out in reference to leastsquares fitting of sinusoids compared to periodogram analysis, that his paper "establishes, apparently for the first time, that (with the proposed modifications) these two methods are exactly equivalent."^{[8]}
Press^{[3]} summarizes the development this way:
A completely different method of spectral analysis for unevenly sampled data, one that mitigates these difficulties and has some other very desirable properties, was developed by Lomb, based in part on earlier work by Barning and Vanicek, and additionally elaborated by Scargle.
In 1989, Michael J. Korenberg of Queen's University in Kingston, Ontario, developed the "fast orthogonal search" method of more quickly finding a nearoptimal decomposition of spectra or other problems,^{[15]} similar to the technique that later became known as orthogonal matching pursuit.
Method variants
The Vaníček method
In the Vaníček method, a discrete data set is approximated by a weighted sum of sinusoids of progressively determined frequencies, using a standard linear regression, or leastsquares fit.^{[16]} The frequencies are chosen using a method similar to Barning's, but going further in optimizing the choice of each successive new frequency by picking the frequency that minimizes the residual after leastsquares fitting (equivalent to the fitting technique now known as matching pursuit with prebackfitting^{[11]}). The number of sinusoids must be less than or equal to the number of data samples (counting sines and cosines of the same frequency as separate sinusoids).
A data vector Φ is represented as a weighted sum of sinusoidal basis functions, tabulated in a matrix A by evaluating each function at the sample times, with weight vector x:
 [math]\displaystyle{ \phi \approx \textbf{A}x }[/math]
where the weight vector x is chosen to minimize the sum of squared errors in approximating Φ. The solution for x is closedform, using standard linear regression:^{[17]}
 [math]\displaystyle{ x = (\textbf{A}^{\mathrm{T}}\textbf{A})^{1}\textbf{A}^{\mathrm{T}}\phi. }[/math]
Here the matrix A can be based on any set of functions that are mutually independent (not necessarily orthogonal) when evaluated at the sample times; for spectral analysis, the functions used are typically sines and cosines evenly distributed over the frequency range of interest. If too many frequencies are chosen in a toonarrow frequency range, the functions will not be sufficiently independent, the matrix will be badly conditioned, and the resulting spectrum will not be meaningful.^{[17]}
When the basis functions in A are orthogonal (that is, not correlated, meaning the columns have zero pairwise dot products), the matrix A^{T}A is a diagonal matrix; when the columns all have the same power (sum of squares of elements), then that matrix is an identity matrix times a constant, so the inversion is trivial. The latter is the case when the sample times are equally spaced and the sinusoids are chosen to be sines and cosines equally spaced in pairs on the frequency interval 0 to a half cycle per sample (spaced by 1/N cycle per sample, omitting the sine phases at 0 and maximum frequency where they are identically zero). This particular case is known as the discrete Fourier transform, slightly rewritten in terms of real data and coefficients.^{[17]}
 [math]\displaystyle{ x = \textbf{A}^{\mathrm{T}}\phi }[/math] (DFT case for N equally spaced samples and frequencies, within a scalar factor)
The Lomb method
Trying to lower the computational burden of the Vaníček method in 1976 ^{[7]} (no longer an issue), Lomb proposed using the above simplification in general, except for pairwise correlations between sine and cosine bases of the same frequency, since the correlations between pairs of sinusoids are often small, at least when they are not too closely spaced. This is essentially the traditional periodogram formulation, but now adopted for use with unevenly spaced samples. The vector x is a good estimate of an underlying spectrum, but since correlations are ignored, Ax is no longer a good approximation to the signal, and the method is no longer a leastsquares method – yet it has continued to be referred to as such.
Rather than just taking dot products of the data with sine and cosine waveforms directly, Scargle modified the standard periodogram formula to first find a time delay [math]\displaystyle{ \tau }[/math] such that this pair of sinusoids would be mutually orthogonal at sample times [math]\displaystyle{ t_j }[/math], and also adjusted for the potentially unequal powers of these two basis functions, to obtain a better estimate of the power at a frequency,^{[3]}^{[8]} which made his modified periodogram method exactly equivalent to Lomb's method. The time delay [math]\displaystyle{ \tau }[/math] is defined by the formula
 [math]\displaystyle{ \tan{2 \omega \tau} = \frac{\sum_j \sin 2 \omega t_j}{\sum_j \cos 2 \omega t_j}. }[/math]
The periodogram at frequency [math]\displaystyle{ \omega }[/math] is then estimated as:
 [math]\displaystyle{ P_x(\omega) = \frac{1}{2} \left( \frac { \left[ \sum_j X_j \cos \omega ( t_j  \tau ) \right] ^ 2} { \sum_j \cos^2 \omega ( t_j  \tau ) } + \frac {\left[ \sum_j X_j \sin \omega ( t_j  \tau ) \right] ^ 2} { \sum_j \sin^2 \omega ( t_j  \tau ) } \right) }[/math]
which Scargle reports then has the same statistical distribution as the periodogram in the evenly sampled case.^{[8]}
At any individual frequency [math]\displaystyle{ \omega }[/math], this method gives the same power as does a leastsquares fit to sinusoids of that frequency, of the form
 [math]\displaystyle{ \phi(t) = A \sin \omega t + B \cos \omega t. }[/math]^{[18]}
The generalized Lomb–Scargle periodogram
The standard Lomb–Scargle periodogram is valid for a model with zero mean. Commonly, this is approximated by subtracting the mean of the data before calculating the periodogram. However, this is an inaccurate assumption when the mean of the model (the fitted sinusoids) is nonzero. The generalized Lomb–Scargle periodogram removes this assumption, and explicitly solves for the mean. In this case, the function fitted is
 [math]\displaystyle{ \phi(t) = A \sin \omega t + B \cos \omega t + C. }[/math]^{[19]}
The generalized Lomb–Scargle periodogram has also been referred to as a floating mean periodogram.^{[20]}
Korenberg's "fast orthogonal search" method
Michael Korenberg of Queen's University in Kingston, Ontario, developed a method for choosing a sparse set of components from an overcomplete set, such as sinusoidal components for spectral analysis, called fast orthogonal search (FOS). Mathematically, FOS uses a slightly modified Cholesky decomposition in a meansquare error reduction (MSER) process, implemented as a sparse matrix inversion.^{[15]}^{[21]} As with the other LSSA methods, FOS avoids the major shortcoming of discrete Fourier analysis, and can achieve highly accurate identifications of embedded periodicities and excels with unequally spaced data; the fast orthogonal search method has also been applied to other problems such as nonlinear system identification.
Palmer's Chisquared method
Palmer has developed a method for finding the bestfit function to any chosen number of harmonics, allowing more freedom to find nonsinusoidal harmonic functions.^{[22]} This method is a fast technique (FFTbased) for doing weighted leastsquares analysis on arbitrarily spaced data with nonuniform standard errors. Source code that implements this technique is available.^{[23]} Because data are often not sampled at uniformly spaced discrete times, this method "grids" the data by sparsely filling a time series array at the sample times. All intervening grid points receive zero statistical weight, equivalent to having infinite error bars at times between samples.
Applications
The most useful feature of the LSSA method is enabling incomplete records to be spectrally analyzed, without the need to manipulate the record or to invent otherwise nonexistent data.
Magnitudes in the LSSA spectrum depict the contribution of a frequency or period to the variance of the time series.^{[13]} Generally, spectral magnitudes defined in the above manner enable the output's straightforward significance level regime.^{[24]} Alternatively, magnitudes in the Vaníček spectrum can also be expressed in dB.^{[25]} Note that magnitudes in the Vaníček spectrum follow βdistribution.^{[26]}
Inverse transformation of Vaníček's LSSA is possible, as is most easily seen by writing the forward transform as a matrix; the matrix inverse (when the matrix is not singular) or pseudoinverse will then be an inverse transformation; the inverse will exactly match the original data if the chosen sinusoids are mutually independent at the sample points and their number is equal to the number of data points.^{[17]} No such inverse procedure is known for the periodogram method.
Implementation
The LSSA can be implemented in less than a page of MATLAB code.^{[27]} In essence:^{[16]}
"to compute the leastsquares spectrum we must compute m spectral values ... which involves performing the leastsquares approximation m times, each time to get [the spectral power] for a different frequency"
I.e., for each frequency in a desired set of frequencies, sine and cosine functions are evaluated at the times corresponding to the data samples, and dot products of the data vector with the sinusoid vectors are taken and appropriately normalized; following the method known as Lomb/Scargle periodogram, a time shift is calculated for each frequency to orthogonalize the sine and cosine components before the dot product, as described by Craymer;^{[17]} finally, a power is computed from those two amplitude components. This same process implements a discrete Fourier transform when the data are uniformly spaced in time and the frequencies chosen correspond to integer numbers of cycles over the finite data record.
This method treats each sinusoidal component independently, or out of context, even though they may not be orthogonal on the data points; it is Vaníček's original method. In contrast, as Craymer explains, it is also possible to perform a full simultaneous or incontext leastsquares fit by solving a matrix equation, partitioning the total data variance between the specified sinusoid frequencies.^{[17]} Such a matrix leastsquares solution is natively available in MATLAB as the backslash operator.^{[28]}
Craymer explains that the simultaneous or incontext method, as opposed to the independent or outofcontext version (as well as the periodogram version due to Lomb), cannot fit more components (sines and cosines) than there are data samples, and further that:^{[17]}
"...serious repercussions can also arise if the selected frequencies result in some of the Fourier components (trig functions) becoming nearly linearly dependent with each other, thereby producing an illconditioned or near singular N. To avoid such ill conditioning it becomes necessary to either select a different set of frequencies to be estimated (e.g., equally spaced frequencies) or simply neglect the correlations in N (i.e., the offdiagonal blocks) and estimate the inverse least squares transform separately for the individual frequencies..."
Lomb's periodogram method, on the other hand, can use an arbitrarily high number of, or density of, frequency components, as in a standard periodogram; that is, the frequency domain can be oversampled by an arbitrary factor.^{[3]}
In Fourier analysis, such as the Fourier transform or the discrete Fourier transform, the sinusoids being fitted to the data are all mutually orthogonal, so there is no distinction between the simple outofcontext dotproductbased projection onto basis functions versus an incontext simultaneous leastsquares fit; that is, no matrix inversion is required to leastsquares partition the variance between orthogonal sinusoids of different frequencies.^{[29]} This method is usually preferred for its efficient fast Fourier transform implementation, when complete data records with equally spaced samples are available.
See also
 Nonuniform discrete Fourier transform
 Orthogonal functions
 SigSpec
 Sinusoidal model
 Spectral density
 Spectral density estimation, for competing alternatives
References
 ↑ Cafer Ibanoglu (2000). Variable Stars As Essential Astrophysical Tools. Springer. ISBN 0792360842. https://books.google.com/books?id=QzGbOiZ3OnkC&q=vanicek+spectral+sinusoids&pg=PA269.
 ↑ ^{2.0} ^{2.1} D. Scott Birney; David Oesper; Guillermo Gonzalez (2006). Observational Astronomy. Cambridge University Press. ISBN 0521853702. https://books.google.com/books?id=cc9L8QWcZWsC&q=LombScargleperiodogram&pg=RA3PA263.
 ↑ ^{3.0} ^{3.1} ^{3.2} ^{3.3} ^{3.4} Press (2007). Numerical Recipes (3rd ed.). Cambridge University Press. ISBN 9780521880688. https://books.google.com/books?id=9GhDHTLzFDEC&q=%22spectral+analysis%22+%22vanicek%22+inauthor:press&pg=PA685.
 ↑ J. Taylor; S. Hamilton (19720320). "Some tests of the Vaníček Method of spectral analysis". Astrophysics and Space Science 17 (2): 357–367. doi:10.1007/BF00642907. Bibcode: 1972Ap&SS..17..357T.
 ↑ M. Omerbashich (20060626). "GaussVanicek spectral analysis of the Sepkoski compendium: no new life cycles". Computing in Science & Engineering 8 (4): 26–30. doi:10.1109/MCSE.2006.68. Bibcode: 2006CSE.....8d..26O.
 ↑ Hans P. A. Van Dongen (1999). "Searching for Biological Rhythms: Peak Detection in the Periodogram of Unequally Spaced Data". Journal of Biological Rhythms 14 (6): 617–620. doi:10.1177/074873099129000984. PMID 10643760.
 ↑ ^{7.0} ^{7.1} ^{7.2} Lomb, N. R. (1976). "Leastsquares frequency analysis of unequally spaced data". Astrophysics and Space Science 39 (2): 447–462. doi:10.1007/BF00648343. Bibcode: 1976Ap&SS..39..447L.
 ↑ ^{8.0} ^{8.1} ^{8.2} ^{8.3} ^{8.4} Scargle, J. D. (1982). "Studies in astronomical time series analysis. II  Statistical aspects of spectral analysis of unevenly spaced data". Astrophysical Journal 263: 835. doi:10.1086/160554. Bibcode: 1982ApJ...263..835S.
 ↑ David Brunt (1931). The Combination of Observations (2nd ed.). Cambridge University Press.
 ↑ Barning, F. J. M. (1963). "The numerical analysis of the lightcurve of 12 Lacertae". Bulletin of the Astronomical Institutes of the Netherlands 17: 22. Bibcode: 1963BAN....17...22B.
 ↑ ^{11.0} ^{11.1} Pascal Vincent; Yoshua Bengio (2002). "Kernel Matching Pursuit". Machine Learning 48: 165–187. doi:10.1023/A:1013955821559. http://www.iro.umontreal.ca/~vincentp/Publications/kmp_mlj.pdf.
 ↑ Y. C. Pati, R. Rezaiifar, and P. S. Krishnaprasad, "Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition," in Proc. 27th Asilomar Conference on Signals, Systems and Computers, A. Singh, ed., Los Alamitos, CA, USA, IEEE Computer Society Press, 1993
 ↑ ^{13.0} ^{13.1} Vaníček, P. (1969). "Approximate spectral analysis by leastsquares fit". Astrophysics and Space Science 4 (4): 387–391. doi:10.1007/BF00651344. Bibcode: 1969Ap&SS...4..387V.
 ↑ Vaníček, P. (1971). "Further development and properties of the spectral analysis by leastsquares". Astrophysics and Space Science 12 (1): 10–33. doi:10.1007/BF00656134. Bibcode: 1971Ap&SS..12...10V.
 ↑ ^{15.0} ^{15.1} Korenberg, M. J. (1989). "A robust orthogonal algorithm for system identification and timeseries analysis". Biological Cybernetics 60 (4): 267–276. doi:10.1007/BF00204124. PMID 2706281.
 ↑ ^{16.0} ^{16.1} Wells, D.E., P. Vaníček, S. Pagiatakis, 1985. Leastsquares spectral analysis revisited. Department of Surveying Engineering Technical Report 84, University of New Brunswick, Fredericton, 68 pages, Available at [1].
 ↑ ^{17.0} ^{17.1} ^{17.2} ^{17.3} ^{17.4} ^{17.5} ^{17.6} Craymer, M.R., The Least Squares Spectrum, Its Inverse Transform and Autocorrelation Function: Theory and Some Applications in Geodesy, Ph.D. Dissertation, University of Toronto, Canada (1998).
 ↑ William J. Emery; Richard E. Thomson (2001). Data Analysis Methods in Physical Oceanography. Elsevier. ISBN 0444507566. https://books.google.com/books?id=gYc4fp_ixmwC&q=vanicek+leastsquares+spectralanalysis+lomb&pg=PA458.
 ↑ M. Zechmeister; M. Kürster (March 2009). "The generalised Lomb–Scargle periodogram. A new formalism for the floatingmean and Keplerian periodograms". Astronomy & Astrophysics 496 (2): 577–584. doi:10.1051/00046361:200811296. Bibcode: 2009A&A...496..577Z.
 ↑ Andrew Cumming; Geoffrey W. Marcy; R. Paul Butler (December 1999). "The Lick Planet Search: Detectability and Mass Thresholds". The Astrophysical Journal 526 (2): 890–915. doi:10.1086/308020. Bibcode: 1999ApJ...526..890C.
 ↑ Korenberg, Michael J.; Brenan, Colin J. H.; Hunter, Ian W. (1997). "Raman Spectral Estimation via Fast Orthogonal Search". The Analyst 122 (9): 879–882. doi:10.1039/a700902j. Bibcode: 1997Ana...122..879K.
 ↑ Palmer, David M. (2009). "A Fast Chisquared Technique For Period Search of Irregularly Sampled Data". The Astrophysical Journal 695 (1): 496–502. doi:10.1088/0004637X/695/1/496. Bibcode: 2009ApJ...695..496P.
 ↑ "David Palmer: The Fast Chisquared Period Search". http://public.lanl.gov/palmer/fastchi.html.
 ↑ Beard, A.G., Williams, P.J.S., Mitchell, N.J. & Muller, H.G. A special climatology of planetary waves and tidal variability, J Atm. SolarTer. Phys. 63 (09), p.801–811 (2001).
 ↑ Pagiatakis, S. Stochastic significance of peaks in the leastsquares spectrum, J of Geodesy 73, p.6778 (1999).
 ↑ Steeves, R.R. A statistical test for significance of peaks in the least squares spectrum, Collected Papers of the Geodetic Survey, Department of Energy, Mines and Resources, Surveys and Mapping, Ottawa, Canada, p.149166 (1981)
 ↑ , Wikidata Q111312009
 ↑ Timothy A. Davis; Kermit Sigmon (2005). MATLAB Primer. CRC Press. ISBN 1584885238. https://books.google.com/books?id=MXWypqcHECkC&q=matlab+leastsquares+backslash&pg=PA12.
 ↑ Darrell Williamson (1999). DiscreteTime Signal Processing: An Algebraic Approach. Springer. ISBN 1852331615. https://books.google.com/books?id=JCKAirWQdqkC&q=fouriertransform+orthogonal+leastsquares&pg=PA314.
External links
 LSSA package freeware download, FORTRAN, Vaníček's leastsquares spectral analysis method, from the University of New Brunswick.
 LSWAVE package freeware download, MATLAB, includes the Vaníček's leastsquares spectral analysis method, from the U.S. National Geodetic Survey.
 LSSA software freeware download (via ftp), FORTRAN, Vaníček's method, from the Natural Resources Canada.
Original source: https://en.wikipedia.org/wiki/Leastsquares spectral analysis.
Read more 