Singular value decomposition | EPFL Graph Search

In linear algebra, the singular value decomposition (SVD) is a factorization of a real or complex matrix. It generalizes the eigendecomposition of a square normal matrix with an orthonormal eigenbasis to any \ m \times n\ matrix. It is related to the polar decomposition. Specifically, the singular value decomposition of an \ m \times n\ complex matrix M is a factorization of the form \ \mathbf{M} = \mathbf{U\Sigma V^}\ , where U is an \ m \times m\ complex unitary matrix, \ \mathbf{\Sigma}\ is an \ m \times n\ rectangular diagonal matrix with non-negative real numbers on the diagonal, V is an n \times n complex unitary matrix, and \ \mathbf{V^}\ is the conjugate transpose of V. Such decomposition always exists for any complex matrix. If M is real, then U and V can be guaranteed to be real orthogonal matrices; in such contexts, the SVD is often denoted \ \mathbf{ U\S

Covariance Estimation for Random Surfaces beyond Separability

Tomas Masák

This thesis focuses on non-parametric covariance estimation for random surfaces, i.e.~functional data on a two-dimensional domain. Non-parametric covariance estimation lies at the heart of functional data analysis, andconsiderations of statistical and computational efficiency often compel the use of separability of the covariance, when working with random surfaces. We seek to provide efficient alternatives to this ambivalent assumption.In Chapter 2, we study a setting where the covariance structure may fail to be separable locally -- either due to noise contamination or due to the presence of a non-separable short-range dependent signal component. That is, the covariance is an additive perturbation of a separable component by a non-separable but banded component. We introduce non-parametric estimators hinging on shifted partial tracing -- a novel concept enjoying strong denoising properties. We illustrate the usefulness of the proposed methodology on a data set of mortality surfaces.In Chapter 3, we propose a distinctive decomposition of the covariance, which allows us to understand separability as an unconventional form of low-rankness. From this perspective, a separable covariance has rank one. Allowing for a higher rank suggests a structured class in which any covariance can be approximated up to an arbitrary precision. The key notion of the partial inner product allows us to generalize the power iteration method to general Hilbert spaces and estimate the aforementioned decomposition from data. Truncation and retention of the leading terms automatically induces a non-parametric estimator of the covariance, whose parsimony is dictated by the truncation level. Advantages of this approach, allowing for estimation beyond separability, are demonstrated on the task of classification of EEG signals.While Chapters 2 and 3 propose several generalizations of separability in the densely sampled regime, Chapter 4 deals with the sparse regime, where the latent surfaces are observed only at few irregular locations. Here, a separable covariance estimator based on local linear smoothers is proposed, which is the first non-parametric utilization of separability in the sparse regime. The assumption of separability reduces the intrinsically four-dimensional smoothing problem into several two-dimensional smoothers and allows the proposed estimator to retain the classical minimax-optimal convergence rate for two-dimensional smoothers. The proposed methodology is used for a qualitative analysis of implied volatility surfaces corresponding to call options, and for prediction of the latent surfaces based on information from the entire data set, allowing for uncertainty quantification. Our quantitative results show that the proposed methodology outperforms the common approach of pre-smoothing every implied volatility surface separately.Throughout the thesis, we put emphasis on computational aspects, since those are the main reason behind the immense popularity of separability. We show that the covariance structures of Chapters 2 and 3 come with no (asymptotic) computational overhead relative to assuming separability. In fact, the proposed covariance structures can be estimated and manipulated with the same asymptotic costs as the separable model. In particular, we develop numerical algorithms that can be used for efficient inversion, as required e.g.~for prediction. All the methods are implemented in R and available on~GitHub.

EPFL2022

Dynamical low rank approximation for uncertainty quantification of time-dependent problems

Eva Vidlicková

The quantification of uncertainties can be particularly challenging for problems requiring long-time integration as the structure of the random solution might considerably change over time. In this respect, dynamical low-rank approximation (DLRA) is very appealing. It can be seen as a reduced basis method, thus solvable at a relatively low computational cost, in which the solution is expanded as a linear combination of a few deterministic functions with random coefficients. The distinctive feature of the DLRA is that both the deterministic functions and random coefficients are computed on the fly and are free to evolve in time, thus adjusting at each time to the current structure of the random solution. This is achieved by suitably projecting the dynamics onto the tangent space of a manifold consisting of all random functions with a fixed rank. In this thesis, we aim at further analysing and applying the DLR methods to time-dependent problems.Our first work considers the DLRA of random parabolic equations and proposes a class of fully discrete numerical schemes.Similarly to the continuous DLRA, our schemes are shown to satisfy a discrete variational formulation.By exploiting this property, we establish the stability of our schemes: we show that our explicit and semi-implicit versions are conditionally stable under a ``parabolic'' type CFL condition which does not depend on the smallest singular value of the DLR solution; whereas our implicit scheme is unconditionally stable. Moreover, we show that, in certain cases, the semi-implicit scheme can be unconditionally stable if the randomness in the system is sufficiently small. The analysis is supported by numerical results showing the sharpness of the obtained stability conditions. The discrete variational formulation is further applied in our second work, which derives a-priori and a-posteriori error estimates for the discrete DLRA of a random parabolic equation obtained by the three newly-proposed schemes. Under the assumption that the right-hand side of the dynamical system lies in the tangent space up to a small remainder, we show that the solution converges with standard convergence rates w.r.t. the time, spatial, and stochastic discretization parameters, with constants independent of singular values.We follow by presenting a residual-based a-posteriori error estimation for a heat equation with a random forcing term and a random diffusion coefficient which is assumed to depend affinely on a finite number of independent random variables. The a-posteriori error estimate consists of four parts: the finite element method error, the time discretization error, the stochastic collocation error, and the rank truncation error. These estimators are then used to drive an adaptive choice of FE mesh, collocation points, time steps, and time-varying rank.The last part of the thesis examines the idea of applying the DLR method in data assimilation problems, in particular the filtering problem. We propose two new filtering algorithms. They both rely on complementing the DLRA with a Gaussian component. More precisely, the DLR portion captures the non-Gaussian features in an evolving low-dimensional subspace through interacting particles, whereas each particle carries a Gaussian distribution on the whole ambient space. We study the effectiveness of these algorithms on a filtering problem for the Lorenz-96 system.

EPFL2022

Random Surface Covariance Estimation by Shifted Partial Tracing

Tomas Masák, Victor Panaretos

The problem of covariance estimation for replicated surface-valued processes is examined from the functional data analysis perspective. Considerations of statistical and computational efficiency often compel the use of separability of the covariance, even though the assumption may fail in practice. We consider a setting where the covariance structure may fail to be separable locally-either due to noise contamination or due to the presence of a nonseparable short-range dependent signal component. That is, the covariance is an additive perturbation of a separable component by a nonseparable but banded component. We introduce nonparametric estimators hinging on the novel concept of shifted partial tracing, enabling computationally efficient estimation of the model under dense observation. Due to the denoising properties of shifted partial tracing, our methods are shown to yield consistent estimators even under noisy discrete observation, without the need for smoothing. Further to deriving the convergence rates and limit theorems, we also show that the implementation of our estimators, including prediction, comes at no computational overhead relative to a separable model. Finally, we demonstrate empirical performance and computational feasibility of our methods in an extensive simulation study and on a real dataset. Supplementary materials for this article are available online.

TAYLOR & FRANCIS INC2022

Covariance Estimation for Random Surfaces beyond Separability

Tomas Masák

EPFL2022

Dynamical low rank approximation for uncertainty quantification of time-dependent problems

Eva Vidlicková

EPFL2022