For any matrix A in R^(m x n) of rank ρ, we present a probability distribution over the entries of A (the element-wise leverage scores of equation (2)) that reveals the most influential entries in the matrix. From a theoretical perspective, we prove that sampling at most s = O ((m + n) ρ^2 ln (m + n)) entries of the ma…
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,657 papers · 148 categories
Trend · papers per month
48 results for “matrix entries”
Improved matrix completion for non-uniformly sampled data.
problem Estimating unobserved entries in a matrix with varying sampling probabilities.
method Developed entry-specific bounds for low-rank matrix completion under structured non-uniform sampling.
result Error bounds for each entry match minimax lower bounds under certain conditions.
We present a novel algebraic combinatorial view on low-rank matrix completion based on studying relations between a few entries with tools from algebraic geometry and matroid theory. The intrinsic locality of the approach allows for the treatment of single entries in a closed theoretical and practical framework. More s…
In this paper, we consider the streaming memory-limited matrix completion problem when the observed entries are noisy versions of a small random fraction of the original entries. We are interested in scenarios where the matrix size is very large so the matrix is very hard to store and manipulate. Here, columns of the o…
The covariance matrix of a -dimensional random variable is a fundamental quantity in data analysis. Given i.i.d. observations, it is typically estimated by the sample covariance matrix, at a computational cost of operations. When are large, this computation may be prohibitively slow. Moreover, …
New spectral methods improve matrix estimation in RL with low-rank structure.
problem Estimating matrices with low-rank structure in reinforcement learning.
method Spectral-based matrix estimation approaches.
result Spectral methods efficiently recover singular subspaces and minimize entry-wise error.
The completion of low rank matrices from few entries is a task with many practical applications. We consider here two aspects of this problem: detectability, i.e. the ability to estimate the rank reliably from the fewest possible random entries, and performance in achieving small reconstruction error. We propose a …
Estimates low-rank distributional matrices from incomplete samples.
problem Matrix completion for distributional entries with limited observed data.
method Kernel mean embeddings, Tucker rank, functional unfolding operators.
result Effective estimator for distributional matrix completion established.
In this paper, we consider matrix completion from non-uniformly sampled entries including fully observed and partially observed columns. Specifically, we assume that a small number of columns are randomly selected and fully observed, and each remaining column is partially observed with uniform sampling. To recover the …
We study low rank matrix and tensor completion and propose novel algorithms that employ adaptive sampling schemes to obtain strong performance guarantees. Our algorithms exploit adaptivity to identify entries that are highly informative for learning the column space of the matrix (tensor) and consequently, our results …
A matrix completion problem, which aims to recover a complete matrix from its partial observations, is one of the important problems in the machine learning field and has been studied actively. However, there is a discrepancy between the mainstream problem setting, which assumes continuous-valued observations, and some…
Causal Matrix Completionecon.EM
New method corrects bias in missing data for matrix completion.
problem Missing data bias in matrix completion.
method Causal model and synthetic nearest neighbors (SNN) method.
result Synthetic nearest neighbors (SNN) method provides consistent and normal estimates.
We consider the problem of reconstructing a low rank matrix from a subset of its entries and analyze two variants of the so-called Alternating Minimization algorithm, which has been proposed in the past. We establish that when the underlying matrix has rank , has positive bounded entries, and the graph $\mathcal{G…
Method uses optimal transport to complete distributional matrices.
problem Matrix completion for distributional data.
method Nearest neighbors in Wasserstein space.
result Method recovers distributions in Wasserstein metric.
Matrix factorization (MF) has been widely used to discover the low-rank structure and to predict the missing entries of data matrix. In many real-world learning systems, the data matrix can be very high-dimensional but sparse. This poses an imbalanced learning problem, since the scale of missing entries is usually much…
A determinantal point process (DPP) is a probabilistic model of set diversity compactly parameterized by a positive semi-definite kernel matrix. To fit a DPP to a given task, we would like to learn the entries of its kernel matrix by maximizing the log-likelihood of the available data. However, log-likelihood is non-co…
Matrix completion is a classical problem in data science wherein one attempts to reconstruct a low-rank matrix while only observing some subset of the entries. Previous authors have phrased this problem as a nuclear norm minimization problem. Almost all previous work assumes no explicit structure of the matrix and uses…
Entry-Specific Matrix Estimation under Arbitrary Sampling Patterns through the Lens of Network Flowsstat.ML
New matrix completion method for arbitrary sampling patterns using network flows.
problem Matrix completion under arbitrary sampling patterns.
method Network flow approach to matrix completion.
result Minimax optimal estimation for individual entries.
Study shows how fast a specific matrix completion method works.
problem Completing a rank-one matrix from a subset of revealed entries.
method Alternating minimization approach for matrix completion.
result Polynomial upper bound on convergence rate.
Predict missing movie ratings or graph embeddings with low rank matrices.
problem Predicting missing entries in a ratings matrix or graph embeddings with known linear relations.
method Low rank matrix completion approach applied to graph embeddings.
result Effective methods for predicting missing entries in matrices and graph embeddings.
Characterizes uncertainty in low-rank matrix completion with noisy data.
problem Uncertainty quantification in low-rank matrix completion with heterogeneous sub-exponential noise.
method Characterizes the distribution of estimated matrix entries under low-rank estimators with heterogeneous sub-exponential noise.
result Explicit formulas for the distribution of estimated matrix entries under Poisson and Binary noise.
A new method for robust matrix completion overcomes limitations of existing approaches.
problem Robust matrix completion from corrupted entries, especially under overparameterization and ill-conditioning.
method Factorization-based iterative algorithm combining Gauss-Newton linearization and outlier removal.
result Theoretical guarantees of exact recovery for suitable assumptions.
New methods recover best rank-r approximations from few entries.
problem Recovering best rank-r approximations from limited data entries.
method Two agnostic approaches: spectral truncation and projected gradient descent.
result Projected gradient descent yields superior performance.
Proposes a new matrix factorization model for interval-valued matrices.
problem Matrix factorization for matrices with entries in a given interval.
method Bounded simplex-structured matrix factorization (BSSMF) with fast algorithm for missing data.
result BSSMF provides a unique decomposition under certain conditions.
PACE-GGM uses Gaussian mechanism for private covariance estimation.
problem Private estimation of covariance matrices in high dimensions.
method Data-adaptive selection of entries, Gaussian mechanism, maximum-entropy reconstruction.
result Consistent improvements in estimation error compared to Gaussian mechanism and baselines.
This paper considers the problem of estimating a low-rank matrix from the observation of all or a subset of its entries in the presence of Poisson noise. When we observe all entries, this is a problem of matrix denoising; when we observe only a subset of the entries, this is a problem of matrix completion. In both case…
Matrix completion is often applied to data with entries missing not at random (MNAR). For example, consider a recommendation system where users tend to only reveal ratings for items they like. In this case, a matrix completion method that relies on entries being revealed at uniformly sampled row and column indices can …
We improve existing results in the field of compressed sensing and matrix completion when sampled data may be grossly corrupted. We introduce three new theorems. 1) In compressed sensing, we show that if the m \times n sensing matrix has independent Gaussian entries, then one can recover a sparse signal x exactly by tr…
CUR matrix decomposition is a randomized algorithm that can efficiently compute the low rank approximation for a given rectangle matrix. One limitation with the existing CUR algorithms is that they require an access to the full matrix A for computing U. In this work, we aim to alleviate this limitation. In particular, …
We consider a challenging multi-label classification problem where both feature matrix $\X$ and label matrix $\Y$ have missing entries. An existing method concatenated $\X$ and $\Y$ as $[\X; \Y]$ and applied a matrix completion (MC) method to fill the missing entries, under the assumption that $[\X; \Y]$ is of low-rank…
We consider the matrix completion problem of recovering a structured matrix from noisy and partial measurements. Recent works have proposed tractable estimators with strong statistical guarantees for the case where the underlying matrix is low--rank, and the measurements consist of a subset, either of the exact individ…
New algorithms speed up attention computation for large models by limiting matrix entries.
problem Efficiently compute attention matrices for large language models.
method Developed algorithms that exploit the structure of the attention matrix to achieve subquadratic time complexity.
result There is a sharp transition at for efficient computation of attention matrices.
New method for symmetric matrix completion using ReLU sampling.
problem Symmetric positive semi-definite low-rank matrix completion with deterministic entry-dependent sampling.
method ReLU sampling, gradient descent with tailored initialization.
result Gradient descent with tailored initialization achieves global minima.
Study one-sided matrix completion with two observations per row.
problem Recover right singular vectors of a low-rank matrix with few observations.
method Impute missing values of and analyze recovery guarantees.
result Provable recovery of with rows, outperforming standard methods.
New method predicts binary matrix entries using empirical Bayes and low-rank structure.
problem Predicting unobserved entries in binary matrices.
method Empirical Bayes method motivated by Efron--Morris estimator, exploiting low-rank structure.
result Superior performance in predictive accuracy, calibration, and efficiency compared to existing methods.
We propose a general framework for reconstructing and denoising single entries of incomplete and noisy entries. We describe: effective algorithms for deciding if and entry can be reconstructed and, if so, for reconstructing and denoising it; and a priori bounds on the error of each entry, individually. In the noiseless…
The paper tackles matrix completion in ultra-sparse sampling, improving imputation accuracy.
problem Matrix completion in ultra-sparse sampling, where each row has only a few entries.
method Estimate row span of matrix or averaged second-moment matrix, normalize and impute missing entries.
result Gradient descent method normalizes and imputes missing entries, achieving low variance and unbiased estimation.
The paper improves matrix completion with auxiliary covariates using LS estimation.
problem Matrix completion with noisy data and auxiliary covariates.
method Iterative least squares estimation with statistical properties derived.
result Asymptotic normal distributions of estimators for low-rank matrix and coefficient matrix.
This paper considers the problem of matrix completion when the observed entries are noisy and contain outliers. It begins with introducing a new optimization criterion for which the recovered matrix is defined as its solution. This criterion uses the celebrated Huber function from the robust statistics literature to do…
New deep learning model for matrix completion combining linear and nonlinear relationships.
problem Matrix completion considering only linear or nonlinear relations, ignoring latent relationships.
method Combines linear and nonlinear models in a latent variables framework, using a deep neural network with two branches for columns and rows, and manifold learning as an auxiliary task.
result Experimental results show the proposed method outperforms state-of-the-art matrix completion methods.
Given a matrix M of low-rank, we consider the problem of reconstructing it from noisy observations of a small, random subset of its entries. The problem arises in a variety of applications, from collaborative filtering (the `Netflix problem') to structure-from-motion and positioning. We study a low complexity algorithm…
Let M be a random (alpha n) x n matrix of rank r<<n, and assume that a uniformly random subset E of its entries is observed. We describe an efficient algorithm that reconstructs M from |E| = O(rn) observed entries with relative root mean square error RMSE <= C(rn/|E|)^0.5 . Further, if r=O(1), M can be reconstructed ex…
New algorithm optimizes positions of CountSketch non-zero entries for better data compression.
problem Optimizing positions of CountSketch non-zero entries for better data compression.
method Learning algorithm that optimizes both values and positions of CountSketch non-zero entries.
result Improves accuracy for low rank approximation and other problems like k-means clustering.
New method for robust matrix completion with mixed data types.
problem Recovering a structured low rank matrix with mixed data types.
method Proposes a computationally feasible statistical approach with strong recovery guarantees for mixed data types.
result Strong recovery guarantees for low rank matrix completion with mixed data types.
In this paper, we study the popularly dubbed matrix completion problem, where the task is to "fill in" the unobserved entries of a matrix from a small subset of observed entries, under the assumption that the underlying matrix is of low-rank. Our contributions herein, enhance our prior work on nuclear norm regularized …
Noisy matrix completion aims at estimating a low-rank matrix given only partial and corrupted entries. Despite substantial progress in designing efficient estimation algorithms, it remains largely unclear how to assess the uncertainty of the obtained estimates and how to perform statistical inference on the unknown mat…
This paper considers the recovery of a low-rank matrix from an observed version that simultaneously contains both (a) erasures: most entries are not observed, and (b) errors: values at a constant fraction of (unknown) locations are arbitrarily corrupted. We provide a new unified performance guarantee on when the natura…
This paper considers the problem of matrix completion when some number of the columns are completely and arbitrarily corrupted, potentially by a malicious adversary. It is well-known that standard algorithms for matrix completion can return arbitrarily poor results, if even a single column is corrupted. One direct appl…