A clustering algorithm uses the left Gram matrix for high dimensional data.
problem Clustering high dimensional data with many features and few objects.
method The algorithm uses the normalized left Gram matrix G = XX'/P to cluster objects based on row means.
result The algorithm provides the most accurate cluster configuration more than twice as often as competitors.
Effective Gram matrix predicts deep network generalization.
problem Understanding and predicting deep network generalization.
method Derived a differential equation governing generalization gap, analyzed with effective Gram matrix.
result Effective Gram matrix accurately predicts test loss during training.
In this paper we show that the matrix of chromatic joins and the Gram matrix of the Temperley-Lieb algebra are similar (after rescaling), with the change of basis given by diagonal matrices.
Layer normalization with activations prevents Gram matrix rank collapse at initialization.
problem Rank collapse in Gram matrices at initialization slows training in deep networks.
method Proved that layer normalization, with activation layers, biases Gram matrix towards identity matrix at exponential rate.
result Layer normalization with activations biases Gram matrix towards identity matrix at exponential rate with depth at initialization.
New method corrects missing data bias in dimension reduction.
problem Missing data complicates high-dimensional data analysis.
method Developed a bias-corrected Gram matrix for heterogeneous missingness.
result Proposed method improves dimension reduction techniques significantly.
Spectral clustering performance depends on eigenvector fluctuations, shown to be Gaussian.
problem Predicting the performance of spectral clustering.
method General spike random matrix model and rotational invariance of noise.
result Fluctuations of eigenvector entries are Gaussian in large-dimensional regime.
Deep kernel processes unify various models using Gram matrices and kernel functions.
problem Unified representation of various deep learning models.
method Defining deep kernel processes with progressively transformed Gram matrices and sampling from inverse Wishart distributions.
result Deep Gaussian processes, BNNs, infinite BNNs, and infinite BNNs with bottlenecks can all be written as deep kernel processes.
This paper extends the convergence rate of DEQs with ReLU to any general activation.
problem Proving global convergence rate for DEQs with general activations.
method Developed a novel population Gram matrix and new form of dual activation with Hermite polynomial expansion.
result Gradient descent converges to a globally optimal solution at a linear rate for DEQs with general activations.
The paper connects Chebyshev polynomials and Gram determinants on Möbius bands.
problem Exploring the relationship between Chebyshev polynomials and Gram determinants on Möbius bands.
method Analyzing Mersenne numbers and Chebyshev polynomials, proving conjectures, and developing algorithms.
result A factor of the Gram determinant supports a conjecture about its closed formula involving Chebyshev polynomials.
Paper proposes a method to recover point configurations from noisy distance data.
problem Recovering point configurations from noisy distance data.
method Robust Euclidean Distance Geometry via Dual Basis (RoDEoDB) algorithm.
result Exact recovery guarantees for point configuration and Gram matrix under mild conditions.
To any compact Riemann surface of genus g one may assign a principally polarized abelian variety of dimension g, the Jacobian of the Riemann surface. The Jacobian is a complex torus, and a Gram matrix of the lattice of a Jacobian is called a period Gram matrix. This paper provides upper and lower bounds for all the ent…
Given a real matrix A with n columns, the problem is to approximate the Gram product AA^T by c << n weighted outer products of columns of A. Necessary and sufficient conditions for the exact computation of AA^T (in exact arithmetic) from c >= rank(A) columns depend on the right singular vector matrix of A. For a Monte-…
We compute Stokes matrices and monodromy for the quantum cohomology of projective spaces. We prove that the Stokes' matrix of the quantum cohomology coincides with the Gram matrix in the theory of derived categories of coherent sheaves.
Gradient descent finds a global minimum in training deep neural networks despite the objective function being non-convex. The current paper proves gradient descent achieves zero training loss in polynomial time for a deep over-parameterized neural network with residual connections (ResNet). Our analysis relies on the p…
Since the invention of word2vec, the skip-gram model has significantly advanced the research of network embedding, such as the recent emergence of the DeepWalk, LINE, PTE, and node2vec approaches. In this work, we show that all of the aforementioned models with negative sampling can be unified into the matrix factoriza…
Paper proposes detecting OOD examples using Gram matrices and in-distribution data.
problem Detecting OOD examples with confidence and without OOD data.
method Characterize activity patterns with Gram matrices and identify anomalies in values.
result High OOD detection rates achieved without OOD data.
Estimates latent norms and Gram matrices for graphs on Euclidean balls.
problem Estimating latent points and their relationships in graphs on Euclidean balls.
method Estimates latent norms and Gram matrices using observed graph data.
result Graphs on Euclidean balls can have power-law degree distributions.
New estimator stabilizes higher-order influence functions for stable statistical inference.
problem Numerical instability in estimating inverse population Gram matrix.
method Proposes a new stabilized higher-order estimator without sample splitting.
result Stabilized estimator exhibits more stable performance and similar statistical guarantees.
Paper improves compressed sensing with prior probability information.
problem Enhancing compressed sensing accuracy with prior information.
method Designing a sensing matrix and sparse recovery algorithm using probability-based prior information.
result Proposed methods outperform existing CS systems in simulations.
Mixed-precision CA-SGD for generalized linear models on GPUs
problem SGD communication bottleneck
method Mixed-precision CA-SGD
result Matches FP32 SGD loss within 0.5% on various problems
A new method uses Gram matrix for efficient multivariate functional principal components.
problem Efficiently estimating eigencomponents of multidimensional functional datasets.
method Proposes using inner-product matrix to estimate eigenelements of multivariate and multidimensional functional datasets.
result Established relationship between eigenelements of covariance operator and inner-product matrix.
Many interesting machine learning problems are best posed by considering instances that are distributions, or sample sets drawn from distributions. Previous work devoted to machine learning tasks with distributional inputs has done so through pairwise kernel evaluations between pdfs (or sample sets). While such an appr…
The paper studies geometric structures on SL(n,R) induced by the Killing form.
problem Understanding geometric structures on SL(n,R) induced by the Killing form.
method Constructing manifolds, studying Poisson-commutation relations, and solving Hamiltonian systems.
result Explicit solutions of Hamiltonian systems for n=2.
A new matrix concentration inequality for random products of matrices.
problem Understanding the behavior of random matrix products under bounded independent positive semidefinite matrices.
method Developed a non-asymptotic concentration inequality for the product of matrices.
result The inequality provides a bound on the deviation of the matrix product from its expected value.
We present in this work a new family of kernels to compare positive measures on arbitrary spaces $\Xcal$ endowed with a positive kernel κ, which translates naturally into kernels between histograms or clouds of points. We first cover the case where $\Xcal$ is Euclidian, and focus on kernels which take into account th…
A new method learns dynamic graph representations from time-varying data.
problem Learning dynamic graph representations from time-varying data.
method Higher-order skip-gram with negative sampling (HOSGNS) for tensor factorization.
result HOSGNS outperforms state-of-the-art methods in downstream tasks.
This paper analyzes error in SKI for Gaussian Processes, providing conditions for linear time inference.
problem Lack of rigorous theoretical error analysis for SKI.
method Proved error bounds for SKI Gram matrix, examined error effects, provided practical guidelines.
result Identified two dimensionality regimes for SKI's scalability-accuracy trade-offs.
We present NN-grams, a novel, hybrid language model integrating n-grams and neural networks (NN) for speech recognition. The model takes as input both word histories as well as n-gram counts. Thus, it combines the memorization capacity and scalability of an n-gram model with the generalization ability of neural network…
Kernel methods are ubiquitous tools in machine learning. However, there is often little reason for the common practice of selecting a kernel a priori. Even if a universal approximating kernel is selected, the quality of the finite sample estimator may be greatly affected by the choice of kernel. Furthermore, when direc…
It is well-known that overparametrized neural networks trained using gradient-based methods quickly achieve small training error with appropriate hyperparameter settings. Recent papers have proved this statement theoretically for highly overparametrized networks under reasonable assumptions. These results either assume…
We simplify word embeddings by removing sigmoid in SGNS, revealing connections to hyperbolic spaces.
problem Improving word embeddings quality and understanding their relationship with hyperbolic spaces.
method Analyzing squashed shifted PMI matrix and its relation to graph properties and hyperbolic geometry.
result Word embeddings can be connected to hyperbolic spaces through squashed shifted PMI matrix.
Researchers use quantum chaos and RMT to analyze turbulence, revealing unique scaling laws.
problem Understanding the statistical structure and scaling laws of turbulence.
method Applied tools from quantum chaos and Random Matrix Theory to analyze turbulence datasets.
result Turbulence Gram matrices exhibit power-law scalings distinct from classical chaos and random data.
Asymptotics of quantum 6j symbols corresponding to a hyperbolic tetrahedra is investigated and the first two leading terms are determined for the case that the tetrahedron has a ideal or ultra-ideal vertex. These terms are given by the volume and the determinant of the Gram matrix of the tetrahedron. A relation to th…
We uncover scaling laws and statistical structure in complex datasets.
problem Understanding universal traits in complex datasets.
method Analogizing data to physical systems, using statistical physics and RMT.
result Real-world datasets and Gaussian data with long-range correlations share the same RMT universality class.
New estimator stabilizes higher-order influence functions for bilinear forms.
problem Stability issues in estimating bilinear forms using higher-order influence functions.
method Proposes a new stabilized higher-order estimator for a class of bilinear forms without sample splitting.
result New estimator exhibits more stable finite-sample performance compared to the empirical higher-order estimator.
The Gram determinant of type A was introduced by Lickorish in his work on invariants of 3 - manifolds. We generalize the theory of the Gram determinant of type A by evaluating, in the annulus, a bilinear form of non-intersecting connections in the disc. The main result provides a closed formula for this Gram determ…
Random feature maps are ubiquitous in modern statistical machine learning, where they generalize random projections by means of powerful, yet often difficult to analyze nonlinear operators. In this paper, we leverage the "concentration" phenomenon induced by random matrix theory to perform a spectral analysis on the Gr…
Eliciting semantic similarity between concepts in the biomedical domain remains a challenging task. Recent approaches founded on embedding vectors have gained in popularity as they risen to efficiently capture semantic relationships The underlying idea is that two words that have close meaning gather similar contexts. …
We investigate the Gram determinant of the bilinear form based on curves in a planar surface, with a focus on the disk with two holes. We prove that the determinant based on n−1 curves divides the determinant based on n curves. Motivated by the work on Gram determinants based on curves in a disk and curves in an an…
Neuc-MDS extends MDS for non-Euclidean data.
problem Limitations of classical MDS with non-Euclidean data.
method Generalizes inner product to symmetric bilinear forms, optimizes eigenvalues of dissimilarity Gram matrix.
result Optimizes STRESS for non-Euclidean data.
Study Gram determinants in knot theory, focusing on a Möbius band determinant.
problem Closed formula for the Gram determinant of type (Mb)1. method Survey of Gram determinants, focusing on a Möbius band determinant.
result Speculation on closed formula for (Mb)1 Gram determinant. Any-gram kernels are a flexible and efficient way to employ bag-of-n-gram features when learning from textual data. They are also compatible with the use of word embeddings so that word similarities can be accounted for. While the original any-gram kernels are implemented on top of tree kernels, we propose a new approa…
Linearized attention fails to converge to NTK limit even at large widths.
problem Understanding the convergence of attention mechanisms to the kernel regime.
method Analyzes linearized attention and its relationship to the NTK limit, considering practical widths and conditions.
result Linearized attention does not converge to its NTK limit at any practical width, revealing a fundamental trade-off.
Study spectral properties of sparse random graphs to recover latent vectors.
problem Recovering latent vectors in sparse random geometric graphs.
method Analyzes spectral concentration and uses orthogonal polynomial expansions, decoupling, and matrix concentration.
result Sharpens spectral norm bounds and proves exact recovery for Gaussian mixture models.
New Gram determinant from Möbius band connects to annulus case.
problem Exploring new Gram determinants in knot theory.
method Skein theoretic approach and bilinear forms.
result Proves important results about new Gram determinant structure.
Spectral graph sparsification preserves geometry of GNN embeddings.
problem Maintaining geometric properties of graph neural network embeddings during sparsification.
method Proving spectral sparsification preserves squared pairwise distances, class means, and covariance structure in embedding space.
result Spectral sparsification preserves the geometry of learned embeddings in GNNs.
The Information Plane theory predicts autoencoders do not compress input information.
problem Understanding the training dynamics of hidden layers in autoencoders.
method Derive a theoretical convergence for the Information Plane of autoencoders using a Gram-matrix based mutual information estimator.
result Ideal autoencoders with a large bottleneck layer size do not compress input information, while a small size causes compression only in the encoder layers.
Method reduces categorical data to lower dimensions using density matrices.
problem Dimensionality reduction for categorical data.
method Density-matrix construction from class-conditional frequencies; spectral embedding.
result Low-dimensional spectral embeddings with controlled rank.