The online problem of computing the top eigenvector is fundamental to machine learning. In both adversarial and stochastic settings, previous results (such as matrix multiplicative weight update, follow the regularized leader, follow the compressed leader, block power method) either achieve optimal regret but run slow,…
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.
169,051 papers · 148 categories
Trend · papers per month
48 results for “Online Eigenvector”
A simple sketch improves online eigenvector and SDP problems.
problem Online eigenvector and semidefinite programming problems.
method Randomized mirror projection and mirror descent analysis.
result Regret bounds similar to MMW with reduced complexity.
We quantify uncertainty in Oja's algorithm's leading eigenvector estimation.
problem Estimating the error of Oja's algorithm's leading eigenvector from streaming data.
method Combining U-statistics, high-dimensional central limit theorems, and multiplier bootstrap.
result Established a weighted χ² approximation for the error between the eigenvector and algorithm output.
Algorithm improves online canonical correlation analysis.
problem Online canonical correlation analysis.
method Stochastic Scaled-Gradient Descent (SSGD) for minimizing expectation over Riemannian manifolds.
result Achieved optimal one-time-scale algorithm with explicit rate of local asymptotic convergence.
In this paper, we propose an acceleration scheme for online memory-limited PCA methods. Our scheme converges to the first eigenvectors in a single data pass. We provide empirical convergence results of our scheme based on the spiked covariance model. Our scheme does not require any predefined parameters such as t…
In this paper, we propose to adopt the diffusion approximation tools to study the dynamics of Oja's iteration which is an online stochastic gradient descent method for the principal component analysis. Oja's iteration maintains a running estimate of the true principal component from streaming data and enjoys less tempo…
Online PCA phase transition depends on , not just .
problem Understanding the phase transition in online PCA.
method Study of Oja's algorithm for online PCA.
result Phase transition in correlation between estimated and true eigenvector.
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.
We present an efficient and practical algorithm for the online prediction of discrete-time linear dynamical systems with a symmetric transition matrix. We circumvent the non-convex optimization problem using improper learning: carefully overparameterize the class of LDSs by a polylogarithmic factor, in exchange for con…
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.
AdaOja improves Oja's algorithm for streaming PCA with adaptive learning rates.
problem Lack of standardized learning rates in Oja's algorithm for streaming PCA.
method Proposes AdaOja, a novel learning rate scheme for Oja's method.
result AdaOja outperforms common learning rate choices and performs comparably to state-of-the-art algorithms.
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…
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…
STVNN models spatiotemporal data using covariance matrices.
problem Challenges in modeling spatiotemporal interactions in multivariate time series.
method Introduces SpatioTemporal coVariance Neural Network (STVNN) that operates on sample covariance matrix and uses joint spatiotemporal convolutions.
result STVNN is stable to online estimation uncertainties and outperforms temporal PCA.
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 algorithm consistently orients eigenvectors for machine learning.
problem Inconsistent eigenvector orientation in machine learning.
method Postprocesses well-established eigen calls to create consistently oriented eigenvectors.
result Interpretable time series of training weights in machine learning models.
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.
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…
Paper tackles small eigen-gap estimation and inference for noisy symmetric matrices.
problem Estimating eigenvectors with small eigen-gap and fine-grained statistical reasoning.
method Eigen-decomposition of asymmetric data matrix, distribution-free procedures, adaptive to heteroscedastic noise.
result Minimax optimal under Gaussian noise, confidence intervals for eigenvalues, small eigen-gap handling.
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.
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.
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.
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 …
Sign equivariant networks improve model expressiveness for spectral geometric learning.
problem Limited expressiveness of sign invariant models for tasks like graph link prediction.
method Developed sign equivariant neural network architectures based on new analytic sign equivariant polynomials.
result Sign equivariant models achieve theoretical benefits in spectral geometric learning tasks.
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.
LEGO estimates tangent spaces more robustly than LPCA in noisy data.
problem Estimating tangent spaces in high-noise settings.
method Spectral method using graph Laplacian eigenvectors and gradient orthogonization.
result LEGO yields more robust tangent space estimates than LPCA.
Algorithm estimates principal eigenvector with adaptive sensing, improving over non-adaptive methods.
problem Estimating principal eigenvector with limited scalar measurements.
method Compressed variant of Oja's algorithm using two adaptive measurements per sample.
result Convergence rate of after iterations, matching information-theoretic lower bound.
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 paper proves Lipschitz regularity of graph Laplacian eigenvectors on random data clouds.
problem Analyzing the regularity of solutions to graph Laplacian equations on random data points.
method Probabilistic coupling of random walks and interpolation method for point clouds to continuum.
result Graph Laplacian eigenvectors are essentially Lipschitz with constants depending on eigenvalues.
Sep-SpectralNet improves SE for broader applicability and scalability.
problem Three main drawbacks of current SE implementations: generalizability, scalability, and eigenvectors separation.
method Sep-SpectralNet extends SpectralNet with an eigenvector separation post-processing step.
result Sep-SpectralNet achieves consistent SE approximation and generalization, enhancing scalability and applicability.