An official website of the United States government
How could the Fourier and other transforms be naturally discovered if one didn't know how to postulate them? In the case of the Discrete Fourier Transform (DFT), we show how it arises naturally out of analysis of circulant matrices. In particular, the DFT can be derived as the change of basis that simultaneously diagonalizes all circulant matrices. In this way, the DFT arises naturally from a linear algebra question about a set of matrices. Rather than thinking of the DFT as a signal transform, it is more natural to think of it as a single change of basis that renders an entire set of mutually-commuting matrices into simple, diagonal forms. The DFT can then be ``discovered'' by solving the eigenvalue/eigenvector problem for a special element in that set. A brief outline is given of how this line of thinking can be generalized to families of linear operators, leading to the discovery of the other common Fourier-type transforms, as well as its connections with group representations theory.
more »
« less
Spectral diagonal ensemble Kalman filters
A new type of ensemble Kalman filter is developed, which is based on replacing the sample covariance in the analysis step by its diagonal in a spectral basis. It is proved that this technique improves the approximation of the covariance when the covariance itself is diagonal in the spectral basis, as is the case, e.g., for a second-order stationary random field and the Fourier basis. The method is extended by wavelets to the case when the state variables are random fields which are not spatially homogeneous. Efficient implementations by the fast Fourier transform (FFT) and discrete wavelet transform (DWT) are presented for several types of observations, including high-dimensional data given on a part of the domain, such as radar and satellite images. Computational experiments confirm that the method performs well on the Lorenz 96 problem and the shallow water equations with very small ensembles and over multiple analysis cycles.
more »
« less
- Award ID(s):
- 1216481
- PAR ID:
- 10047267
- Date Published:
- Journal Name:
- Nonlinear Processes in Geophysics
- Volume:
- 22
- Issue:
- 4
- ISSN:
- 1607-7946
- Page Range / eLocation ID:
- 485 to 497
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Data assimilation methods often also employ the same discrete dynamical model used to evolve the state estimate in time to propagate an approximation of the state estimation error covariance matrix. Four‐dimensional variational methods, for instance, evolve the covariance matrix implicitly via discrete tangent linear dynamics. Ensemble methods, while not forming this matrix explicitly, approximate its evolution at low rank from the evolution of the ensemble members. Such approximate evolution schemes for the covariance matrix imply an approximate evolution of the estimation error variances along its diagonal. For states that satisfy the advection equation, the continuity equation, or related hyperbolic partial differential equations (PDEs), the estimation error variance itself satisfies a known PDE, so the accuracy of the various approximations to the variances implied by the discrete covariance propagation can be determined directly. Experiments conducted by the atmospheric chemical constituent data assimilation community have indicated that such approximate variance evolution can be highly inaccurate. Through careful analysis and simple numerical experiments, we show that such poor accuracy must be expected, due to the inherent nature of discrete covariance propagation, coupled with a special property of the continuum covariance dynamics for states governed by these types of hyperbolic PDE. The intuitive explanation for this inaccuracy is that discrete covariance propagation involves approximating diagonal elements of the covariance matrix with combinations of off‐diagonal elements, even when there is a discontinuity in the continuum covariance dynamics along the diagonal. Our analysis uncovers the resulting error terms that depend on the ratio of the grid spacing to the correlation length, and these terms become very large when correlation lengths begin to approach the grid scale, for instance, as gradients steepen near the diagonal. We show that inaccurate variance evolution can manifest itself as both spurious loss and gain of variance.more » « less
-
Abstract How fast a state of a system converges to a stationary state is one of the fundamental questions in science. Some Markov chains and random walks on finite groups are known to exhibit the non-asymptotic convergence to a stationary distribution, called the cutoff phenomenon. Here, we examine how quickly a random quantum circuit could transform a quantum state to a Haar-measure random quantum state. We find that random quantum states, as stationary states of random walks on a unitary group, are invariant under the quantum Fourier transform (QFT). Thus the entropic uncertainty of random quantum states has balanced Shannon entropies for the computational basis and the QFT basis. By calculating the Shannon entropy for random quantum states and the Wasserstein distances for the eigenvalues of random quantum circuits, we show that the cutoff phenomenon occurs for the random quantum circuit. It is also demonstrated that the Dyson-Brownian motion for the eigenvalues of a random unitary matrix as a continuous random walk exhibits the cutoff phenomenon. The results here imply that random quantum states could be generated with shallow random circuits.more » « less
-
We address the problem of learning a sparsifying graph Fourier transform (GFT) for compressible signals on directed graphs (digraphs). Blending the merits of Fourier and dictionary learning representations, the goal is to obtain an orthonormal basis that captures spread modes of signal variation with respect to the underlying network topology, and yields parsimonious representations of bandlimited signals. Accordingly, we learn a data-adapted dictionary by minimizing a spectral dispersion criterion over the achievable frequency range, along with a sparsity-promoting regularization term on the GFT coefficients of training signals. An iterative algorithm is developed which alternates between minimizing a smooth objective over the Stiefel manifold, and soft-thresholding the graph-spectral domain representations of the signals in the training set. A frequency analysis of temperature measurements recorded across the contiguous United States illustrates the merits of the novel GFT design.more » « less
-
null (Ed.)Summary Estimation of mean and covariance functions is fundamental for functional data analysis. While this topic has been studied extensively in the literature, a key assumption is that there are enough data in the domain of interest to estimate both the mean and covariance functions. We investigate mean and covariance estimation for functional snippets in which observations from a subject are available only in an interval of length strictly, and often much, shorter than the length of the whole interval of interest. For such a sampling plan, no data is available for direct estimation of the off-diagonal region of the covariance function. We tackle this challenge via a basis representation of the covariance function. The proposed estimator enjoys a convergence rate that is adaptive to the smoothness of the underlying covariance function, and has superior finite-sample performance in simulation studies.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.5194/npg-22-485-2015
