We develop and analyze efficient "coordinate-wise" methods for finding the leading eigenvector, where each step involves only a vector-vector product. We establish global convergence with overall runtime guarantees that are at least as good as Lanczos's method and dominate it for slowly decaying spectrum. Our methods a…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
48 results for “dominant eigenvectors”
We prove a central limit theorem for the components of the eigenvectors corresponding to the largest eigenvalues of the normalized Laplacian matrix of a finite dimensional random dot product graph. As a corollary, we show that for stochastic blockmodel graphs, the rows of the spectral embedding of the normalized La…
Explainable, Stable, and Scalable Graph Convolutional Networks for Learning Graph Representationcs.LG
New GCNs solve graph embedding problems efficiently and interpretably.
problem Graph embedding for scalable and interpretable machine learning.
method Proposed two GCNs: CAFE-GCN and sphere-GCN, based on constrained optimization.
result Both GCNs yield good approximations of dominant eigenvectors and perform dimensionality reduction.
In this paper, we apply tools from the random matrix theory (RMT) to estimates of correlations across volatility of various assets in the S&P 500. The volatility inputs are estimated by modeling price fluctuations as GARCH(1,1) process. The corresponding correlation matrix is constructed. It is found that the distribut…
The problem of estimating sparse eigenvectors of a symmetric matrix attracts a lot of attention in many applications, especially those with high dimensional data set. While classical eigenvectors can be obtained as the solution of a maximization problem, existing approaches formulate this problem by adding a penalty te…
Complex network analysis reveals dominant stocks in financial stock returns correlations.
problem Inferring financial stock returns correlations from complex network analysis.
method Simulated geometric Brownian motion for stocks, complex network analysis, eigenvector centrality, clustering.
result Returns correlation matrix is dominated by stocks with high eigenvector centrality and clustering.
Sparse PCA is a widely used technique for high-dimensional data analysis. In this paper, we propose a new method called low-rank principal eigenmatrix analysis. Different from sparse PCA, the dominant eigenvectors are allowed to be dense but are assumed to have a low-rank structure when matricized appropriately. Such a…
Biological neurons learn tensor decompositions of higher-order correlations using nonlinear Hebbian plasticity.
problem Learning higher-order correlations in biological neurons.
method Introduce and study generalized nonlinear Hebbian learning rules.
result Neurons can learn tensor eigenvectors of higher-order input correlation tensors.
We analyzed cross-correlations between price fluctuations of global financial indices (20 daily stock indices over the world) and local indices (daily indices of 200 companies in the Korean stock market) by using random matrix theory (RMT). We compared eigenvalues and components of the largest and the second largest ei…
The paper extends hypothesis testing to non-diagonalizable matrices, improving network statistics inference.
problem Testing on non-diagonalizable matrices for network statistics.
method Generalizes Wald and t-tests to non-symmetric matrices, controlling convergence rates.
result Improved inference on network statistics from directed networks.
This paper considers the sparse eigenvalue problem, which is to extract dominant (largest) sparse eigenvectors with at most non-zero components. We propose a simple yet effective solution called truncated power method that can approximately solve the underlying nonconvex optimization problem. A strong sparse recove…
Kernel dimensionality reduction (KDR) algorithms find a low dimensional representation of the original data by optimizing kernel dependency measures that are capable of capturing nonlinear relationships. The standard strategy is to first map the data into a high dimensional feature space using kernels prior to a projec…
Spectral clustering refers to a family of unsupervised learning algorithms that compute a spectral embedding of the original data based on the eigenvectors of a similarity graph. This non-linear transformation of the data is both the key of these algorithms' success and their Achilles heel: forming a graph and computin…
Study eigenvector overlaps in large Gaussian matrices, simplifying for GOE.
problem Investigate eigenvector overlaps in large Gaussian matrices.
method Analysis of eigenvector flow under Dyson Brownian motion.
result Explicit computation of limiting rescaled mean squared overlaps.
Machine learning models perform better with location coordinates alone, not Moran Eigenvectors.
problem Improving machine learning models for spatial data.
method Examined Moran Eigenvectors as additional spatial features in machine learning models using synthetic datasets.
result Machine learning models using only location coordinates achieve better accuracies than eigenvector-based approaches.
Paper addresses eigenvector perturbation in small eigen-gap scenarios.
problem Fine-grained behavior of eigenvectors in the presence of small eigen-gaps.
method Develops de-biased estimators for linear functions of an unknown eigenvector.
result Achieves minimax lower bounds for a family of scenarios, even with small eigen-gaps.
We calculate eigenvector overlaps between intersecting time periods of covariance matrices.
problem Analyzing overlapping time periods in covariance matrices.
method Girko linearisation and extended local laws.
result Computed eigenvector overlaps for intersecting time intervals.
In many applications, one has side information, e.g., labels that are provided in a semi-supervised manner, about a specific target region of a large data set, and one wants to perform machine learning and data analysis tasks "nearby" that prespecified target region. For example, one might be interested in the clusteri…
Novel approximation hierarchy for sparse quadratic programs.
problem Sparse Quadratic Programs with Cardinality Constraints.
method Exploits rank-dominating eigenvectors for min-max optimization over binary variables.
result Efficient screening of nonzero elements with scalable optimization algorithms.
The correlation matrix is the key element in optimal portfolio allocation and risk management. In particular, the eigenvectors of the correlation matrix corresponding to large eigenvalues can be used to identify the market mode, sectors and style factors. We investigate how these eigenvalues depend on the time scale of…
A low-rank ensemble Kalman filter for elliptic observationsphysics.flu-dyn
A new EnKF method for elliptic PDEs reduces dimensionality for accurate state estimation.
problem Elliptic PDEs in fluid flows make traditional EnKF regularization ineffective.
method Low-rank factorization of the Kalman gain based on the Jacobian spectrum.
result Inference can be performed in a low-dimensional subspace of the state space.
In spectral clustering, one defines a similarity matrix for a collection of data points, transforms the matrix to get the Laplacian matrix, finds the eigenvectors of the Laplacian matrix, and obtains a partition of the data using the leading eigenvectors. The last step is sometimes referred to as rounding, where one ne…
We study the problem asking if one can embed manifolds into finite dimensional Euclidean spaces by taking finite number of eigenvector fields of the connection Laplacian. This problem is essential for the dimension reduction problem in massive data analysis. Singer-Wu proposed the vector diffusion map which embeds mani…
New metric tensor field on symmetric matrices simplifies eigenvector computation.
problem Complex eigenvector computation for 2x2 symmetric matrices.
method Introducing a metric tensor field on the space of symmetric matrices, resulting in a curved manifold.
result Parallel transport simplifies eigenvector computation for one-parameter families of matrices.
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.
New neural architectures invariant to sign flips and basis symmetries for graph representation learning.
problem Learning invariant graph representations from eigenvectors.
method SignNet and BasisNet neural architectures that are invariant to sign flips and basis symmetries.
result Proven to be universal, approximating any continuous function of eigenvectors with desired invariances.
New algorithm updates eigenvectors of evolving graphs efficiently.
problem Updating eigenvectors of dynamic graphs.
method Subspace projection based on Rayleigh-Ritz projections.
result Strong performance in eigenvector approximation and downstream tasks.
How many samples are sufficient to guarantee that the eigenvectors and eigenvalues of the sample covariance matrix are close to those of the actual covariance matrix? For a wide family of distributions, including distributions with finite second moment and distributions supported in a centered Euclidean ball, we prove …
New theory for eigenvectors of generalized Laplacian matrices, addressing dependency issues.
problem Dependency in random matrix theory hinders eigenvector analysis for latent embeddings.
method Introduces generalized Laplacian matrices and a new asymptotic theory framework.
result Established asymptotic normalities for spiked eigenvectors and eigenvalues.
Fast algorithm recovers principal eigenvector from noisy matrices.
problem Recovering the first principal eigenvector from noisy positive semidefinite matrices.
method Cone projected power iteration algorithm.
result Achieves polynomial time complexity and small error for certain convex cones.
This paper develops the exact linear relationship between the leading eigenvector of the unnormalized modularity matrix and the eigenvectors of the adjacency matrix. We propose a method for approximating the leading eigenvector of the modularity matrix, and we derive the error of the approximation. There is also a comp…
New method improves subspace iteration for eigenvectors in machine learning.
problem Computing eigenvectors for large-scale problems in machine learning.
method Subspace iteration with norm convergence analysis.
result Deterministic bounds and practical stopping criterion for improved performance.
The paper explores how kernel eigenalignments affect generalization in KRR.
problem Achieving robust generalization in kernel methods.
method Direct connection between generalization and matrix eigenvectors/eigenvalues, focusing on finite-sample settings.
result Strong generalization requires increasing eigenvector alignment, eigenvalue magnitude, or gaps between eigenvalues.
Improved spectral clustering with fewer eigenvectors performs better.
problem Improving spectral clustering performance under weaker conditions.
method Tighter analysis and using fewer eigenvectors for embedding.
result Spectral clustering can produce better results with fewer eigenvectors.
New insights into spectral clustering reveal strong connections within eigenvectors.
problem Clustering on graphs when there are two underlying clusters.
method Analyzes the eigenvector corresponding to the second largest eigenvalue of the adjacency matrix.
result Vertices with extreme values in the eigenvector are more reliably classified.
Perturbation of the Eigenvectors of the Graph Laplacian: Application to Image Denoisingphysics.data-an
The original contributions of this paper are twofold: a new understanding of the influence of noise on the eigenvectors of the graph Laplacian of a set of image patches, and an algorithm to estimate a denoised set of patches from a noisy image. The algorithm relies on the following two observations: (1) the low-index e…
We characterize the contractions that are similar to the backward shift in the Hardy space . This characterization is given in terms of the geometry of the eigenvector bundles of the operators.
Graph convolutional networks fail to use eigenvectors beyond the first, unlike spectral embedding.
problem Understanding when graph convolutional networks fail compared to spectral embedding.
method Presented a simple generative model to illustrate failure.
result Graph convolutional networks fail to use eigenvectors beyond the first in certain graphs.
We provide new examples of diffusion operators in dimension 2 and 3 which have orthogonal polynomials as eigenvectors. Their construction rely on the finite subgroups of O(3) and their invariant polynomials.
Deep ReLU networks escape from the origin via saddle points with a low-rank bias.
problem Understanding the dynamics of gradient descent in deep ReLU networks.
method Analysis of escape directions and singular values of weight matrices.
result The first singular value of the -th layer weight matrix is at least larger than any other singular value.
Study eigenvalues and eigenvectors in neural networks, focusing on signal propagation.
problem Characterize signal eigenvalues and eigenvectors in neural networks.
method Characterizes signal eigenvalues and eigenvectors for a nonlinear spiked covariance model.
result Provides precise quantitative characterizations of signal eigenvalues and eigenvectors in neural networks.
The paper tackles learning symmetries in data without expert knowledge.
problem Learning symmetries in data from raw data without prior knowledge.
method Develops methods to select eigenvectors for orthogonal symmetries and compares their effectiveness.
result The problem of learning symmetries is as hard as the graph automorphism problem in the worst case, but can be simplified with certain restrictions.
This paper aims to address two fundamental challenges arising in eigenvector estimation and inference for a low-rank matrix from noisy observations: (1) how to estimate an unknown eigenvector when the eigen-gap (i.e. the spacing between the associated eigenvalue and the rest of the spectrum) is particularly small; (2) …
SPECTRE uses spectral conditioning to generate larger graphs without mode collapse.
problem Overcoming expressivity and mode collapse in one-shot graph generators.
method SPECTRE generates graph Laplacian spectrum and eigenvectors to model graph structure.
result SPECTRE outperforms state-of-the-art deep autoregressive generators in fidelity and speed.
New method improves covariance estimation for weighted samples.
problem Improving covariance estimation for weighted sample data.
method Asymptotic non-linear shrinkage formulas for covariance and precision matrix estimators of weighted sample covariances.
result Asymptotic non-linear shrinkage formulas for covariance and precision matrix estimators of weighted sample covariances.
Linear Shape Deformation Models with Local Support Using Graph-based Structured Matrix Factorisationcs.CV
Representing 3D shape deformations by linear models in high-dimensional space has many applications in computer vision and medical imaging, such as shape-based interpolation or segmentation. Commonly, using Principal Components Analysis a low-dimensional (affine) subspace of the high-dimensional shape space is determin…
An analysis of Cross-correlations in South African Market datacond-mat.stat-mech
We apply random matrix theory to compare correlation matrix estimators C obtained from emerging market data. The correlation matrices are constructed from 10 years of daily data for stocks listed on the Johannesburg Stock Exchange (JSE) from January 1993 to December 2002. We test the spectral properties of C against ra…
We prove a central limit theorem for the components of the largest eigenvectors of the adjacency matrix of a finite-dimensional random dot product graph whose true latent positions are unknown. In particular, we follow the methodology outlined in \citet{sussman2012universally} to construct consistent estimates for the …