Invariant subspace problem | EPFL Graph Search

In the field of mathematics known as functional analysis, the invariant subspace problem is a partially unresolved problem asking whether every bounded operator on a complex Banach space sends some non-trivial closed subspace to itself. Many variants of the problem have been solved, by restricting the class of bounded operators considered or by specifying a particular class of Banach spaces. The problem is still open for separable Hilbert spaces (in other words, each example, found so far, of an operator with no non-trivial invariant subspaces is an operator that acts on a Banach space that is not isomorphic to a separable Hilbert space). History The problem seems to have been stated in the mid-1900s after work by Beurling and von Neumann, who found (but never published) a positive solution for the case of compact operators. It was then posed by Paul Halmos for the case of operators T such that T^2 is compact. This was resolved affirmatively, for t

AN OBSTRUCTION TO l(p)-DIMENSION

Nicolas Monod, Henrik Densing Petersen

Let G be any group containing an infinite elementary amenable subgroup and let 2 < p < infinity. We construct an exhaustion of l(p) G by closed invariant subspaces which all intersect trivially a fixed non-trivial closed invariant subspace. This is an obstacle to l(p)-dimension and gives an answer to a question of Gaboriau.

Annales Inst Fourier2014

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

Optimizing Quantize-Map-and-Forward Relaying for Gaussian Diamond Networks

Christina Fragouli, Ayan Sengupta, I-Hsiang Wang

We evaluate the information-theoretic achievable rates of Quantize-Map-and-Forward (QMF) relaying schemes over Gaussian

N

-relay diamond networks. Focusing on vector Gaussian quantization at the relays, our goal is to understand how close to the cutset upper bound these schemes can achieve in the context of diamond networks, and how much benefit is obtained by optimizing the quantizer distortions at the relays. First, with noise-level quantization, we point out that the worst-case gap from the cutset upper bound is

(N+\log_2 N)

bits/s/Hz. A better universal quantization level found without using channel state information (CSI) leads to a sharpened gap of

\log_2 N + \log_2(1+N) + N\log_2(1 + 1/N)

bits/s/Hz. On the other hand, it turns out that finding the optimal distortion levels depending on the channel gains is a non-trivial problem in the general

N

-relay setup. We manage to solve the two-relay problem and the symmetric

N

-relay problem analytically, and show the improvement via numerical evaluations both in static as well as slow-fading channels.

2012