Search

In many applications it is useful to replace the Moore-Penrose pseudoinverse (MPP) by a different generalized inverse with more favorable properties. We may want, for example, to have many zero entries, but without giving up too much of the stability of the MPP. One way to quantify stability is by how much the Frobenius norm of a generalized inverse exceeds that of the MPP. In this paper we derive finite-size concentration bounds for the Frobenius norm of ℓp-minimal general inverses of iid Gaussian matrices, with 1 ≤ p ≤ 2. For p = 1 we prove exponential concentration of the Frobenius norm of the sparse pseudoinverse; for p = 2, we get a similar concentration bound for the MPP. Our proof is based on the convex Gaussian min-max theorem, but unlike previous applications which give asymptotic results, we derive finite-size bounds. [ABSTRACT FROM AUTHOR]

In many applications it is useful to replace the Moore--Penrose pseudoinverse (MPP) by a different generalized inverse with more favorable properties. We may want, for example, to have many zero entries, but without giving up too much of the stability of the MPP. One way to quantify stability is by how much the Frobenius norm of a generalized inverse exceeds that of the MPP. In this paper we derive finite-size concentration bounds for the Frobenius norm of lp-minimal general inverses of iid Gaussian matrices, with 1 ≤ p ≤ 2. For p = 1 we prove exponential concentration of the Frobenius norm of the sparse pseudoinverse; for p = 2, we get a similar concentration bound for the MPP. Our proof is based on the convex Gaussian min-max theorem, but unlike previous applications which give asymptotic results, we derive finite-size bounds. [ABSTRACT FROM AUTHOR]

In this paper, we derive an explicit form of the convolution theorem for functions on an n-sphere. Our motivation comes from the design of a probability density estimator for n-dimensional random vectors. We propose a probability density function (pdf) estimation method that uses the derived convolution result on Sn. Random samples are mapped onto the -sphere and estimation is performed in the new domain by convolving the samples with the smoothing kernel density. The convolution is carried out in the spectral domain. Samples are mapped between the n-sphere and the n-dimensional Euclidean space by the generalized stereographic projection. We apply the proposed model to several synthetic and real-world data sets and discuss the results. [ABSTRACT FROM AUTHOR]

Graph neural networks (GNNs) excel in modeling relational data such as biological, social, and transportation networks, but the underpinnings of their success are not well understood. Traditional complexity measures from statistical learning theory fail to account for observed phenomena like the double descent or the impact of relational semantics on generalization error. Motivated by experimental observations of "transductive" double descent in key networks and datasets, we use analytical tools from statistical physics and random matrix theory to precisely characterize generalization in simple graph convolution networks on the contextual stochastic block model. Our results illuminate the nuances of learning on homophilic versus heterophilic data and predict double descent whose existence in GNNs has been questioned by recent work. We show how risk is shaped by the interplay between the graph noise, feature noise, and the number of training labels. Our findings apply beyond stylized models, capturing qualitative trends in real-world GNNs and datasets. As a case in point, we use our analytic insights to improve performance of state-of-the-art graph convolution networks on heterophilic datasets. [ABSTRACT FROM AUTHOR]

Injectivity plays an important role in generative models where it enables inference; in inverse problems and compressed sensing with generative priors it is a precursor to well posedness. We establish sharp characterizations of injectivity of fully-connected and convolutional ReLU layers and networks. First, through a layerwise analysis, we show that an expansivity factor of two is necessary and sufficient for injectivity by constructing appropriate weight matrices. We show that global injectivity with iid Gaussian matrices, a commonly used tractable model, requires larger expansivity between 3.4 and 10.5. We also characterize the stability of inverting an injective network via worst-case Lipschitz constants of the inverse. We then use arguments from differential topology to study injectivity of deep networks and prove that any Lipschitz map can be approximated by an injective ReLU network. Finally, using an argument based on random projections, we show that an end-to-end--rather than layerwise--doubling of the dimension suffices for injectivity. Our results establish a theoretical basis for the study of nonlinear inverse and inference problems using neural networks. [ABSTRACT FROM AUTHOR]