Paper studies efficient regression for dynamic graphs.
problem Regression over dynamic graphs.
method Update-efficient matrix embedding, O(nm) time complexity for updates.
result Exact optimal solution can be updated efficiently in dynamic graphs.
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 “matrix updates”
In this paper, we propose an online algorithm to compute matrix factorizations. Proposed algorithm updates the dictionary matrix and associated coefficients using a single observation at each time. The algorithm performs low-rank updates to dictionary matrix. We derive the algorithm by defining a simple objective funct…
Unified approach combining gradient descent and multiplicative updates.
problem Combining gradient descent and multiplicative updates for machine learning.
method Introduces hypentropy and a family of matrix-based updates.
result Derives tight regret bounds for the new family of updates.
Fast Convolutive Nonnegative Matrix Factorization Through Coordinate and Block Coordinate Updatescs.LG
New algorithms improve NMF for extracting patterns from time series data.
problem Extracting short-lived temporal motifs from high-dimensional time series data.
method Extended HALS and ANLS algorithms for CNMF model.
result Improved performance on large-scale data compared to multiplicative updates.
NMF with specific constraints is equivalent to LDA.
problem Dimensionality reduction of non-negative data.
method NMF with normalization constraints and Dirichlet prior.
result NMF with these constraints is equivalent to LDA.
A new optimization algorithm for Gaussian Variational Inference on precision matrices.
problem Complex models with positive definite constraints on covariance matrices.
method Manifold Gaussian Variational Bayes (MGVBP) with natural gradient updates.
result Empirically validated as a feasible and efficient solution for VI in complex models.
PSI-LinUCB improves scalability for large recommender systems.
problem Efficiently training and inferring for large action spaces in recommender systems.
method Represent inverse design matrix as diagonal + low-rank correction, derive stable rank-1 and batched updates, use projector-splitting integrator.
result Demonstrated effectiveness on recommender system datasets, achieving scalable training and inference.
A Non-commutative Extension of Lee-Seung's Algorithm for Positive Semidefinite Factorizationsmath.OC
An algorithm for computing positive semidefinite factorizations of matrices.
problem Computing positive semidefinite factorizations of matrices.
method Non-commutative extension of Lee-Seung's algorithm (Matrix Multiplicative Update, MMU).
result The MMU algorithm ensures PSD updates and achieves critical points.
In this paper we consider a general matrix factorization model which covers a large class of existing models with many applications in areas such as machine learning and imaging sciences. To solve this possibly nonconvex, nonsmooth and non-Lipschitz problem, we develop a non-monotone alternating updating method based o…
Nonnegative matrix factorization (NMF) has attracted much attention in the last decade as a dimension reduction method in many applications. Due to the explosion in the size of data, naturally the samples are collected and stored distributively in local computational nodes. Thus, there is a growing need to develop algo…
A new method for machine learning updates reduces complexity and improves robustness.
problem Stochastic gradient updates are inefficient and sensitive to feature scaling.
method Incremental Gauss-Newton Descent (IGND) reduces the need for matrix operations and improves robustness.
result IGND improves robustness to sensitivity scaling and can be competitive with common stochastic optimizers.
The paper updates SVD of evolving matrices using projection techniques.
problem Updating the rank-k truncated SVD of evolving matrices.
method Projection viewpoint, building subspaces to approximate singular vectors.
result The proposed algorithm leads to higher accuracy, especially for large singular values.
Matrix completion, where we wish to recover a low rank matrix by observing a few entries from it, is a widely studied problem in both theory and practice with wide applications. Most of the provable algorithms so far on this problem have been restricted to the offline setting where they provide an estimate of the unkno…
The paper introduces MU for NMF with -divergences and disjoint constraints.
problem Nonnegative matrix factorization with constraints.
method Design multiplicative updates for NMF based on -divergences with disjoint constraints.
result Multiplicative updates satisfy constraints and decrease the objective function.
A new black-box optimizer using implicit natural gradient.
problem Efficient optimization for complex, computationally intensive problems.
method Stochastic update with implicit natural gradient of an exponential-family distribution.
result Theoretical convergence rate for convex functions and continuous non-differentiable functions.
In this paper, we extend the -CNMF to two dimensions and derive exact multiplicative updates for its factors. The new updates generalize and correct the nonnegative matrix factor deconvolution previously proposed by Schmidt and Mørup. We show by simulation that the updates lead to a monotonically decreasing -dive…
Efficiently factorizes coupled matrix tensor data for better accuracy and speed.
problem Poor computation efficiency in existing N-CMTF algorithms.
method Column-wise element selection to prevent frequent gradient updates.
result More accurate and computationally efficient factorization.
New algorithm provably converges to second-order stationary points in NMF.
problem Understanding convergence to local minima in NMF.
method Multiplicative weight update dynamics, concurrent updates, and simplex reduction.
result Provable convergence to second-order stationary points.
This work presents GROUSE (Grassmanian Rank-One Update Subspace Estimation), an efficient online algorithm for tracking subspaces from highly incomplete observations. GROUSE requires only basic linear algebraic manipulations at each iteration, and each subspace update can be performed in linear time in the dimension of…
In this paper, we provide a novel construction of the linear-sized spectral sparsifiers of Batson, Spielman and Srivastava [BSS14]. While previous constructions required running time [BSS14, Zou12], our sparsification routine can be implemented in almost-quadratic running time . The funda…
Nonnegative matrix factorization (NMF), a dimensionality reduction and factor analysis method, is a special case in which factor matrices have low-rank nonnegative constraints. Considering the stochastic learning in NMF, we specifically address the multiplicative update (MU) rule, which is the most popular, but which h…
New algorithm speeds up NMF with -divergence.
problem Efficiently factorize nonnegative matrices with -divergence.
method Joint majorization-minimization with multiplicative updates.
result Significant reduction in computation time for NMF.
New method improves matrix factorization speed and accuracy.
problem Matrix factorization optimization problems suffer from biased solutions and lack of convergence guarantees.
method Proposes a novel Bregman distance for matrix factorization, enabling non-alternating schemes with convergence proof.
result Convergence to a stationary point proved for matrix factorization problems.
Improved MMWU algorithm achieves instance-optimal regret bound for matrix LEA.
problem Matrix Learning from Expert Advice problem.
method Developed a general potential-based framework for matrix LEA, using a new Jensen's trace inequality.
result Achieved instance-optimal regret bound of .
A Flexible and Efficient Algorithmic Framework for Constrained Matrix and Tensor Factorizationstat.ML
We propose a general algorithmic framework for constrained matrix and tensor factorization, which is widely used in signal processing and machine learning. The new framework is a hybrid between alternating optimization (AO) and the alternating direction method of multipliers (ADMM): each matrix factor is updated in tur…
Study on network-valued processes with asynchronous updates, proving consistency in community and changepoint estimation.
problem Understanding the behavior of network-valued stochastic processes with asynchronous updates.
method Analysis of concentration properties of aggregated adjacency and Laplacian matrices for lazy network-valued stochastic processes.
result Demonstrates consistency of estimators in community and changepoint estimation problems.
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.
Efficient CD algorithms on matrix manifolds for optimization problems.
problem Optimization on Riemannian manifolds with computational efficiency.
method Developed coordinate descent algorithms for various matrix manifolds, updating only a few variables at each iteration.
result Proposed algorithms achieve low cost per iteration and a more efficient variant via first-order approximation.
New optimizer designs respect symmetry, improving deep learning models.
problem Optimizers lack respect for symmetry in neural networks.
method Introduce symmetry-compatible principle for optimizer design.
result Symmetry-compatible optimizers improve model performance.
Efficient algorithm removes redundant nodes and obsolete samples in machine learning.
problem Pruning redundant nodes and removing obsolete training samples in machine learning.
method Deduced decremented learning algorithms from incremental learning algorithms, using inverse Cholesterol factor and unitary transformation.
result Proposed decremented learning algorithms efficiently prune redundant nodes and remove obsolete training samples.
Muon replaces matrix gradient with polar factor, optimizing flat spectrum updates
problem Optimization bias in matrix updates
method Using polar factor of gradient
result Muon update maximizes entropy among bounded updates
New ELM algorithms reduce computation time and complexity.
problem Efficient computation of extreme learning machine (ELM) algorithms.
method Developed inverse-free ELM algorithms using recursive matrix inverse and inverse LDL' factorization.
result Proposed algorithms significantly reduce computational complexity.
Sparse Inverse Covariance Estimation (SICE) is useful in many practical data analyses. Recovering the connectivity, non-connectivity graph of covariates is classified amongst the most important data mining and learning problems. In this paper, we introduce a novel SICE approach using adaptive thresholding. Our method i…
Nonnegative matrix factorization (NMF) is now a common tool for audio source separation. When learning NMF on large audio databases, one major drawback is that the complexity in time is O(FKN) when updating the dictionary (where (F;N) is the dimension of the input power spectrograms, and K the number of basis spectra),…
Bayesian model improves categorization of explosions from sparse data.
problem Challenges in categorizing explosions from limited data.
method Bayesian update to Event Categorization Matrix model with Bayesian Decision Theory.
result Consistent gains in overall accuracy and lower false negative rates.
Recurrent Neural Networks (RNNs) are designed to handle sequential data but suffer from vanishing or exploding gradients. Recent work on Unitary Recurrent Neural Networks (uRNNs) have been used to address this issue and in some cases, exceed the capabilities of Long Short-Term Memory networks (LSTMs). We propose a simp…
Efficiently completes low-rank matrices with nearly linear time complexity.
problem Completing low-rank matrices from a few observed entries.
method Robust alternating minimization framework with approximate updates.
result Achieves nearly linear time complexity in matrix completion.
Developed a Particle-Gibbs sampler for Bayesian feature allocation models.
problem Intractable exact inference in Bayesian feature allocation models.
method Particle-Gibbs sampler for feature allocation matrix updates.
result PG sampler improves performance of feature allocation models.
KrADagrad: Kronecker Approximation-Domination Gradient Preconditioned Stochastic Optimizationstat.ML
A new optimization method reduces memory and compute requirements for deep learning.
problem Memory and compute constraints in second-order stochastic optimizers for deep learning.
method Proposes KrAD, a novel factorization to approximate inverse Fisher matrix without inversion, leading to KrADagrad.
result Improves performance over Shampoo for 32-bit precision and comparable/generalization on real datasets.
The problem of outlier detection is extremely challenging in many domains such as text, in which the attribute values are typically non-negative, and most values are zero. In such cases, it often becomes difficult to separate the outliers from the natural variations in the patterns in the underlying data. In this paper…
Tensor networks and RNNs are equivalent, improving wave function encoding.
problem Efficiently encoding quantum states in neural networks.
method Generalized RNN architecture for tensor networks, supporting polynomial time wave function evaluation.
result Tensorial RNNs can encode quantum states with lower bond dimensions and higher accuracy.
New method for inference on covariates in NMF with random effects.
problem Formal inference for covariate effects in NMF with non-negativity constraints.
method NMF-RE model with random effects, ridge updates, df-based cap, asymptotic linearization, wild bootstrap.
result Valid inference on covariates with non-negativity constraint, avoiding degeneracy.
QBVI uses natural gradients for efficient Bayesian learning.
problem Efficient Bayesian learning in complex models.
method Natural gradient updates in a black-box framework for exponential-family distributions.
result QBVI framework is effective for a wide range of Bayesian inference problems.
Pion optimizes LLMs by preserving weight matrix singular values.
problem Training large language models (LLMs) with standard optimizers leads to unstable weight matrices.
method Pion uses orthogonal transformations to update weight matrices, preserving their singular values.
result Pion offers a stable alternative to standard optimizers for LLM pretraining and finetuning.
NGD improves multivariate Gaussian inference by optimizing Fisher information.
problem Efficiently optimizing multivariate Gaussian models.
method Natural Gradient Descent applied to multivariate Gaussian parameters.
result NGD updates are more efficient for symmetric covariance matrices.
This paper analyzes how periodic and soft target updates stabilize linear Q-learning.
problem Theoretical explanation of stabilization mechanisms for linear Q-learning.
method Exact analysis using switched linear system dynamics and the joint spectral radius.
result Periodic and soft target updates can guarantee convergence to the exact projected Q-Bellman solution under specific conditions.
New algorithm reduces complexity for SPD manifold optimization.
problem Efficiently minimize functions over SPD manifold.
method Low-complexity Riemannian subspace descent with sparse updates.
result Innovative updates avoid costly matrix operations.
Improves scalability and robustness of dynamic graph clustering.
problem Scalability and robustness issues in matrix factorization methods for dynamic graphs.
method Temporal separated matrix factorization, bi-clustering regularization, selective embedding updating.
result Demonstrated scalability, robustness, and effectiveness on synthetic and real-world benchmarks.