Helmut Bölcskei

Last Name

Bölcskei

First Name

Helmut

ORCID

0000-0003-3047-5149

Organisational unit

03610 - Boelcskei, Helmut / Boelcskei, Helmut

Show all metadata

Search Results

Publications1 - 10 of 36

Affine symmetries and neural network identifiability
Vlačić, Verner; Bölcskei, Helmut (2021)
Advances in Mathematics
We address the following question of neural network identifiability: Suppose we are given a function and a nonlinearity ρ. Can we specify the architecture, weights, and biases of all feed-forward neural networks with respect to ρ giving rise to f? Existing literature on the subject suggests that the answer should be yes, provided we are only concerned with finding networks that satisfy certain “genericity conditions”. Moreover, the identified networks are mutually related by symmetries of the nonlinearity. For instance, the tanh function is odd, and so flipping the signs of the incoming and outgoing weights of a neuron does not change the output map of the network. The results known hitherto, however, apply either to single-layer networks, or to networks satisfying specific structural assumptions (such as full connectivity), as well as to specific nonlinearities. In an effort to answer the identifiability question in greater generality, we consider arbitrary nonlinearities with potentially complicated affine symmetries, and we show that the symmetries can be used to find a rich set of networks giving rise to the same function f. The set obtained in this manner is, in fact, exhaustive (i.e., it contains all networks giving rise to f) unless there exists a network “with no internal symmetries” giving rise to the identically zero function. This result can thus be interpreted as an analog of the rank-nullity theorem for linear operators. We furthermore exhibit a class of “tanh-type” nonlinearities (including the tanh function itself) for which such a network does not exist, thereby solving the identifiability question for these nonlinearities in full generality and settling an open problem posed by Fefferman in [6]. Finally, we show that this class contains nonlinearities with arbitrarily complicated symmetries.
Discrete deep feature extraction: A theory and new architectures
Wiatowski, Thomas; Tschannen, Michael; Stanic, Aleksandar; et al. (2016)
SAM Research Report
First steps towards a mathematical theory of deep convolutional neural networks for feature extraction were made—for the continuous-time case— in Mallat, 2012, and Wiatowski and Bölcskei, 2015. This paper considers the discrete case, introduces new convolutional neural network architectures, and proposes a mathematical framework for their analysis. Specifically, we establish deformation and translation sensitivity results of local and global nature, and we investigate how certain structural properties of the input signal are reflected in the corresponding feature vectors. Our theory applies to general filters and general Lipschitz-continuous non-linearities and pooling operators. Experiments on handwritten digit classification and facial landmark detection—including feature importance evaluation—complement the theoretical findings.
Capacity scaling laws in MIMO relay networks
Bölcskei, Helmut; Nabar, Rohit U.; Oyman, Özgür; et al. (2006)
IEEE Transactions on Wireless Communications
The use of multiple antennas at both ends of a wireless link, popularly known as multiple-input multiple-output (MIMO) wireless, has been shown to offer significant improvements in spectral efficiency and link reliability through spatial multiplexing and space-time coding, respectively. This paper demonstrates that similar performance gains can be obtained in wireless relay networks employing terminals with MIMO capability. We consider a setup where a designated source terminal communicates with a designated destination terminal, both equipped with M antennas, assisted by K single-antenna or multiple-antenna relay terminals using a half-duplex protocol. Assuming perfect channel state information (CSI) at the destination and the relay terminals and no CSI at the source, we show that the corresponding network capacity scales as C = (M/2) log(K) + O(1) for fixed M, arbitrary (but fixed) number of (transmit and receive) antennas N at each of the relay terminals, and K rarr infin. We propose a protocol that assigns each relay terminal to one of the multiplexed data streams forwarded in a "doubly coherent" fashion (through matched filtering) to the destination terminal. It is shown that this protocol achieves the cut-set upper bound on network capacity for fixed M and K rarr infin (up to an O(1)-term) by employing independent stream decoding at the destination terminal. Our protocol performs inter-stream interference cancellation in a completely decentralized fashion, thereby orthogonalizing the effective MIMO channel between source and destination terminals. Finally, we discuss the case where the relay terminals do not have CSI and show that simple amplify-and-forward relaying, asymptotically in K, for fixed M and fixed N ges 1, turns the relay network into a point-to-point MIMO link with high-SNR capacity C = (M/2) log(SNR) + O(1), demonstrating that the use of relays as active scatterers can recover spatial multiplexing gain in poor scattering environments.
Uncertainty relations and sparse signal recovery
Riegler, Erwin; Bölcskei, Helmut (2021)
Information-Theoretic Methods in Data Science
This chapter provides an introduction to uncertainty relations underlying sparse signal recovery. We start with the seminal work by Donoho and Stark (1989), which defines uncertainty relations as upper bounds on the operator norm of the band-limitation operator followed by the time-limitation operator, generalize this theory to arbitrary pairs of operators, and then develop, out of this generalization, the coherence-based uncertainty relations due to Elad and Bruckstein (2002), plus uncertainty relations in terms of concentration of the 1-norm or 2-norm. The theory is completed with set-theoretic uncertainty relations which lead to best possible recovery thresholds in terms of a general measure of parsimony, the Minkowski dimension. We also elaborate on the remarkable connection between uncertainty relations and the “large sieve,” a family of inequalities developed in analytic number theory. We show how uncertainty relations allow one to establish fundamental limits of practical signal recovery problems such as inpainting, declipping, super-resolution, and denoising of signals corrupted by impulse noise or narrowband interference.
Lossy compression of general random variables
Riegler, Erwin; Koliander, Günther; Bölcskei, Helmut (2023)
Information and Inference: A Journal of the IMA
This paper is concerned with the lossy compression of general random variables, specifically with rate-distortion theory and quantization of random variables taking values in general measurable spaces such as, e.g. manifolds and fractal sets. Manifold structures are prevalent in data science, e.g. in compressed sensing, machine learning, image processing and handwritten digit recognition. Fractal sets find application in image compression and in the modeling of Ethernet traffic. Our main contributions are bounds on the rate-distortion function and the quantization error. These bounds are very general and essentially only require the existence of reference measures satisfying certain regularity conditions in terms of small ball probabilities. To illustrate the wide applicability of our results, we particularize them to random variables taking values in (i) manifolds, namely, hyperspheres and Grassmannians and (ii) self-similar sets characterized by iterated function systems satisfying the weak separation property.
Almost lossless analog signal separation
Stotz, David; Riegler, Erwin; Bölcskei, Helmut (2013)
2013 IEEE International Symposium on Information Theory
We propose an information-theoretic framework for analog signal separation. Specifically, we consider the problem of recovering two analog signals from a noiseless sum of linear measurements of the signals. Our framework is inspired by the groundbreaking work of Wu and Verdú (2010) on almost lossless analog compression. The main results of the present paper are a general achievability bound for the compression rate in the analog signal separation problem, an exact expression for the optimal compression rate in the case of signals that have mixed discrete-continuous distributions, and a new technique for showing that the intersection of generic subspaces with subsets of sufficiently small Minkowski dimension is empty. This technique can also be applied to obtain a simplified proof of a key result in Wu and Verdú (2010).
The SIMO pre-log can be larger than the SISO pre-log
Morgenshtern, Veniamin I.; Durisi, Giuseppe; Bölcskei, Helmut (2010)
2010 IEEE International Symposium on Information Theory
We establish a lower bound on the noncoherent capacity pre-log of a temporally correlated Rayleigh block-fading single-input multiple-output (SIMO) channel. Surprisingly, when the covariance matrix of the channel satisfies a certain technical condition related to the cardinality of its smallest set of linearly dependent rows, this lower bound reveals that the capacity pre-log in the SIMO case is larger than that in the single-input single-output (SISO) case.
Lossless analog compression
Alberti, Giovanni; Bölcskei, Helmut; De Lellis, Camillo; et al. (2019)
IEEE Transactions on Information Theory
Joint sparsity with different measurement matrices
Heckel, Reinhard; Bölcskei, Helmut (2012)
2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton)
We consider a generalization of the multiple measurement vector (MMV) problem, where the measurement matrices are allowed to differ across measurements. This problem arises naturally when multiple measurements are taken over time, e.g., and the measurement modality (matrix) is time-varying. We derive probabilistic recovery guarantees showing that—under certain (mild) conditions on the mea surement matrices—`2/`1-norm minimization and a variant of orthogonal matching pursuit fail with a probability that decays exponentially in the number of measurements. This allows us to conclude that, perhaps surprisingly, recovery performance does not suffer from the individual measurements being taken through different measurement matrices. What is more, recov ery performance typically benefits (significantly) from diversity in the measurement matrices; we specify conditions under which such improvements are obtained. These results continue to hold when the measurements are subject to (bounded) noise.
Noisy subspace clustering via thresholding
Heckel, Reinhard; Bölcskei, Helmut (2013)
2013 IEEE International Symposium on Information Theory
We consider the problem of clustering noisy high-dimensional data points into a union of low-dimensional subspaces and a set of outliers. The number of subspaces, their dimensions, and their orientations are unknown. A probabilistic performance analysis of the thresholding-based subspace clustering (TSC) algorithm introduced recently in [1] shows that TSC succeeds in the noisy case, even when the subspaces intersect. Our results reveal an explicit tradeoff between the allowed noise level and the affinity of the subspaces. We furthermore find that the simple outlier detection scheme introduced in [1] provably succeeds in the noisy case.

Publications1 - 10 of 36

Helmut Bölcskei

Last Name

First Name

ORCID

Organisational unit

Filters

Search Results