Singular value

Summary

In mathematics, in particular functional analysis, the singular values, or s-numbers of a compact operator T: X \rightarrow Y acting between Hilbert spaces X and Y, are the square roots of the (necessarily non-negative) eigenvalues of the self-adjoint operator T^T (where T^ denotes the adjoint of T). The singular values are non-negative real numbers, usually listed in decreasing order (σ1(T), σ2(T), …). The largest singular value σ1(T) is equal to the operator norm of T (see Min-max theorem). If T acts on Euclidean space \Reals ^n, there is a simple geometric interpretation for the singular values: Consider the image by T of the unit sphere; this is an ellipsoid, and the lengths of its semi-axes are the singular values of T (the figure provides an example in \Reals^2). The singular values are the absolute values of the eigenvalues of a normal matri

Official source

https://en.wikipedia.org/wiki/Singular_value

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (11)

Related publications

Related people (1)

Related people

Related units (1)

Related units

Related concepts (16)

Related concepts

Related courses (25)

Related courses

Related lectures (38)

Related lectures

In this thesis we deal with three different but connected questions. Firstly (cf. Chapter 2) we make a systematic study of the generalized notions of convexity for sets. We study the notions of polyconvex, quasiconvex and rank one convex set. We remark that these notions are nowadays well known in the context of functions, but not in the context of sets. Following the classical approach, we give precise definitions of generalized convex sets and we study several issues, in this generalized sense, as the concept of convex hull, Carathéodory and separation theorems and the notion of extremal point. Secondly we have studied some differential inclusions of the form The method we have used to solve this kind of problems is the Baire categories method developed by Dacorogna-Marcellini [14]. Known sufficient conditions for this problem are connected to the generalized convex hull of the set E. In Chapter 3, we compute the rank one convex hull of some matrix sets to obtain, in Chapter 4, existence results. Namely, we have considered the problem of finding u : Ω ⊂ Rn → RN with Dirichlet boundary condition such that Φ (Du(x)) ∈ {α, β}, a.e. x ∈ Ω, Φ being an arbitrary quasi-affine function. We have also considered the problem of finding u : Ω ⊂ Rn → Rn such that where λ1(Du) ≤...≤ λn(Du) are the singular values of Du ∈ Rn×n. Finally, in Chapter 5, we deal with several minimizing problems of the form Denoting by Qf the quasiconvex envelope of f, we verify that solving the equation Qf(Du(x)) = f(Du(x)), a.e. x ∈ Ω is, under some conditions, sufficient to ensure the existence of solution of (P). The differential inclusions that we consider in Chapter 4 are helpful to solve some equations of the form (2) and thus, it allows us to solve problems of type (P). In particular, we have considered the problem (P) with f(ξ) = g(Φ(ξ)), ∀ ξ ∈ RN×n Φ being an arbitrary quasi-affine function.

EPFL2006

, ,

We consider the phase retrieval problem of reconstructing a n -dimensional real or complex signal X ⋆ from m (possibly noisy) observations Y μ = | ∑ n i = 1 Φ μ i X ⋆ i / √ n | , for a large class of correlated real and complex random sensing matrices Φ , in a high-dimensional setting where m , n → ∞ while α = m / n = Θ ( 1 ) . First, we derive sharp asymptotics for the lowest possible estimation error achievable statistically and we unveil the existence of sharp phase transitions for the weak- and full-recovery thresholds as a function of the singular values of the matrix Φ . This is achieved by providing a rigorous proof of a result first obtained by the replica method from statistical mechanics. In particular, the information-theoretic transition to perfect recovery for full-rank matrices appears at α = 1 (real case) and α = 2 (complex case). Secondly, we analyze the performance of the best-known polynomial time algorithm for this problem --- approximate message-passing--- establishing the existence of statistical-to-algorithmic gap depending, again, on the spectral properties of Φ . Our work provides an extensive classification of the statistical and algorithmic thresholds in high-dimensional phase retrieval for a broad class of random matrices.

Curran Associates, Inc.2020

Fast hierarchical solvers for symmetric eigenvalue problems

Ana Susnjara

In this thesis we address the computation of a spectral decomposition for symmetric banded matrices. In light of dealing with large-scale matrices, where classical dense linear algebra routines are not applicable, it is essential to design alternative techniques that take advantage of data properties. Our approach is based upon exploiting the underlying hierarchical low-rank structure in the intermediate results. Indeed, we study the computation in the hierarchically off-diagonal low rank (HODLR) format of two crucial tools: QR decomposition and spectral projectors, in order to devise a fast spectral divide-and-conquer method. In the first part we propose a new method for computing a QR decomposition of a HODLR matrix, where the factor R is returned in the HODLR format, while Q is given in a compact WY representation. The new algorithm enjoys linear-polylogarithmic complexity and is norm-wise accurate. Moreover, it maintains the orthogonality of the Q factor. The approximate computation of spectral projectors is addressed in the second part. This problem has raised some interest in the context of linear scaling electronic structure methods. There the presence of small spectral gaps brings difficulties to existing algorithms based on approximate sparsity. We propose a fast method based on a variant of the QDWH algorithm, and exploit that QDWH applied to a banded input generates a sequence of matrices that can be efficiently represented in the HODLR format. From the theoretical side, we provide an analysis of the structure preservation in the final outcome. More specifically, we derive a priori decay bounds on the singular values in the off-diagonal blocks of spectral projectors. Consequently, this shows that our method, based on data-sparsity, brings benefits in terms of memory requirements in comparison to approximate sparsity approaches, because of its logarithmic dependence on the spectral gap. Numerical experiments conducted on tridiagonal and banded matrices demonstrate that the proposed algorithm is robust with respect to the spectral gap and exhibits linear-polylogarithmic complexity. Furthermore, it renders very accurate approximations to the spectral projectors even for very large matrices. The last part of this thesis is concerned with developing a fast spectral divide-and-conquer method in the HODLR format. The idea behind this technique is to recursively split the spectrum, using invariant subspaces associated with its subsets. This allows to obtain a complete spectral decomposition by solving the smaller-sized problems. Following Nakatsukasa and Higham, we combine our method for the fast computation of spectral projectors with a novel technique for finding a basis for the range of such a HODLR matrix. The latter strongly relies on properties of spectral projectors, and it is analyzed theoretically. Numerical results confirm that the method is applicable for large-scale matrices, and exhibits linear-polylogarithmic complexity.

EPFL2018

Fast hierarchical solvers for symmetric eigenvalue problems

Ana Susnjara

EPFL2018