Tensor completion is a problem of filling the missing or unobserved entries of partially observed tensors. Due to the multidimensional character of tensors in describing complex datasets, tensor completion algorithms and their applications have received wide attention and achievement in areas like data mining, computer…
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,742 papers · 148 categories
Trend · papers per month
48 results for “complete algorithm”
Paper proposes a clustering algorithm for nonnegative data.
problem Clustering nonnegative data in disjoint subspaces.
method Simple algorithm to cluster nonnegative data.
result Matrix completion algorithm outperforms standard methods.
New algorithm for nonnegative tensor completion with linear convergence rate.
problem Tensor completion without known optimal sample complexity rate.
method Integer optimization using a specific 0-1 polytope gauge norm.
result Achieves information-theoretic rate with linear convergence.
Paper explores robustness of CCS model for matrix completion.
problem Robustness of cross-concentrated sampling model against sparse outliers.
method Proposes Robust CUR Completion (RCURC) algorithm for efficient non-convex iterative matrix completion.
result Empirical validation of RCURC's efficiency and robustness in synthetic and real datasets.
Open problem: Establishing bounds for Cayley-table completion to discover discrete algorithmic axioms.
problem Discovering discrete algorithmic axioms missing in deep learning.
method Cayley-table completion as a testbed for algorithmic complexity minimization.
result Formal exact recovery bounds for Cayley-table completion.
Proposes a transductive matrix completion method with calibration for multi-task learning.
problem Improving multi-task learning with multiple related data sources.
method Transductive matrix completion with calibration constraint.
result The proposed algorithm recovers incomplete feature and target matrices with improved results.
Develops a two-stage approach for robust tensor completion of visual data.
problem Estimating missing values in high-order data with outliers.
method Coarse-to-fine framework and M-estimator-based robust tensor ring recovery.
result Superior performance compared to state-of-the-art robust algorithms.
Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actionscs.LG
Polynomial-time RL algorithm for constant actions under linear Bellman completeness.
problem Efficient online reinforcement learning with few actions.
method Polynomial-time algorithm based on linear function approximation.
result First computationally efficient algorithm for RL with constant actions under linear Bellman completeness.
In this paper, we review the problem of matrix completion and expose its intimate relations with algebraic geometry, combinatorics and graph theory. We present the first necessary and sufficient combinatorial conditions for matrices of arbitrary rank to be identifiable from a set of matrix entries, yielding theoretical…
New method for exact matrix completion with reduced observation complexity.
problem Exact recovery of matrices with high coherence.
method Adaptive sampling method and relation to sparsest vector of column and row spaces.
result Exact recovery of -coherent column space matrices with much smaller observation complexity.
Low-rank tensor completion problem aims to recover a tensor from limited observations, which has many real-world applications. Due to the easy optimization, the convex overlapping nuclear norm has been popularly used for tensor completion. However, it over-penalizes top singular values and lead to biased estimations. I…
Two complete knot invariants from diagrams, finite or infinite.
problem Classifying knots completely.
method Constructed two invariants from knot diagrams, finite or infinite.
result Finite set reveals knotting number.
Matrix completion is a widely used technique for image inpainting and personalized recommender system, etc. In this work, we focus on accelerating the matrix completion using faster randomized singular value decomposition (rSVD). Firstly, two fast randomized algorithms (rSVD-PI and rSVD- BKI) are proposed for handling …
We give an algorithm for completing an order- symmetric low-rank tensor from its multilinear entries in time roughly proportional to the number of tensor entries. We apply our tensor completion algorithm to the problem of learning mixtures of product distributions over the hypercube, obtaining new algorithmic result…
A new image completion method inspired by brain cells.
problem Image restoration from corrupted data.
method Biologically-inspired sub-Riemannian model with frequency and phase.
result Completion of two-dimensional images using cortical cell responses.
We obtain the first polynomial-time algorithm for exact tensor completion that improves over the bound implied by reduction to matrix completion. The algorithm recovers an unknown 3-tensor with incoherent, orthogonal components in from randomly observed entries of the tensor…
New algorithm completes nonnegative tensors with fewer samples and faster convergence.
problem Tensor completion tension between sample complexity and computational complexity.
method Integer programming and Blended Conditional Gradients algorithm.
result Achieves information-theoretic sample complexity rate with practical convergence.
With the huge influx of various data nowadays, extracting knowledge from them has become an interesting but tedious task among data scientists, particularly when the data come in heterogeneous form and have missing information. Many data completion techniques had been introduced, especially in the advent of kernel meth…
One of the current issues in Brain-Computer Interface is how to deal with noisy Electroencephalography measurements organized as multidimensional datasets. On the other hand, recently, significant advances have been made in multidimensional signal completion algorithms that exploit tensor decomposition models to captur…
We propose a set of convex low rank inducing norms for a coupled matrices and tensors (hereafter coupled tensors), which shares information between matrices and tensors through common modes. More specifically, we propose a mixture of the overlapped trace norm and the latent norms with the matrix trace norm, and then, w…
Develops a Gaussian-based message-passing algorithm for noisy matrix completion.
problem Noisy matrix completion problems.
method Gaussian parameterized belief propagation algorithm.
result Advantages over traditional methods in non-Gaussian noise scenarios.
New tensor completion method converges linearly and is highly practical.
problem Recovering low-rank tensors from sparse observations.
method Adapted alternating minimization to tensor setting.
result Linear convergence even with highly correlated factors.
New tensor completion method reduces impact of outliers.
problem Recover tensors from incomplete data with outliers.
method Proposes a new correntropy-based objective function and half-quadratic minimization.
result Demonstrates robust performance with real and synthetic data.
New algorithm improves tensor completion performance.
problem Tensor completion for partially observed data.
method Adaptive ADMM optimization framework for low-rank tensor completion.
result New method outperforms conventional techniques in NMSE.
A new framework improves tensor completion accuracy by considering numerical priors.
problem Tensor completion accuracy loss due to ignoring numerical priors.
method Generalized CP Decomposition Tensor Completion (GCDTC) framework incorporating numerical priors.
result GCDTC framework outperforms state-of-the-arts in non-negative tensor completion.
New method solves robust matrix completion using nonlinear equations.
problem Recover low rank and sparse matrices from incomplete observations.
method Transforms problem into solving a system of nonlinear equations, then uses the alternative direction method.
result Algorithm converges linearly to the true solution under proper assumptions.
Introduces t-CCS for flexible tensor sampling.
problem Lack of flexibility in tensor sampling methods.
method Tensor Cross-Concentrated Sampling (t-CCS).
result Effective tensor recovery from t-CCS samples.
New algorithm identifies causal relationships from graphs, even with selection bias.
problem Identifying causal relationships from graphs with selection bias.
method Developed a measure-theoretic version of Pearl's causal calculus and a sound, complete identification algorithm.
result General measure-theoretic version of causal calculus allows for identification of causal relationships under selection bias.
New algorithm completes noisy tensors quickly and accurately.
problem Reconstructing low-rank tensors from incomplete and noisy data.
method Two-stage nonconvex gradient descent algorithm.
result Achieves near-optimal statistical guarantees and linear time complexity.
Matrix completion is a basic machine learning problem that has wide applications, especially in collaborative filtering and recommender systems. Simple non-convex optimization algorithms are popular and effective in practice. Despite recent progress in proving various non-convex algorithms converge from a good initial …
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.
Matrix completion has attracted much interest in the past decade in machine learning and computer vision. For low-rank promotion in matrix completion, the nuclear norm penalty is convenient due to its convexity but has a bias problem. Recently, various algorithms using nonconvex penalties have been proposed, among whic…
New algorithms solve nonconvex-concave minimax problems without parameter knowledge.
problem Solving nonconvex-concave minimax problems efficiently.
method Three completely parameter-free single-loop algorithms.
result Achieve optimal iteration complexity for nonconvex-concave minimax problems.
We consider a generalization of low-rank matrix completion to the case where the data belongs to an algebraic variety, i.e. each data point is a solution to a system of polynomial equations. In this case the original matrix is possibly high-rank, but it becomes low-rank after mapping each column to a higher dimensional…
Detecting Free Products in the Mapping Class Group of Punctured Disks via Dynnikov Coordinatesmath.GT
Algorithm detects free products in disk mapping class groups.
problem Detecting free products in mapping class groups of punctured disks.
method Algorithm based on Dynnikov coordinates to verify completeness and reveal free product structure.
result Algorithm determines exact structure of free products generated by Dehn twists.
Scalable method completes ill-conditioned matrices from few samples.
problem Matrix completion from few samples for ill-conditioned matrices.
method Iterative algorithm combining IRLS, smoothing Newton, and proximal gradient methods.
result Local quadratic convergence rate and well-conditioned linear systems.
We develop an empirical Bayes (EB) algorithm for the matrix completion problems. The EB algorithm is motivated from the singular value shrinkage estimator for matrix means by Efron and Morris (1972). Since the EB algorithm is essentially the EM algorithm applied to a simple model, it does not require heuristic paramete…
A new algorithm completes rank-1 tensors with minimal samples and time.
problem Completing rank-1 tensors with minimal samples and time.
method Gauss-Jordan on random linear systems.
result Gauss-Jordan algorithm uses samples and runs in time.
This work establishes always-valid risk bounds for online matrix completion.
problem Challenges in establishing always-valid concentration inequalities for online matrix completion.
method Combines non-asymptotic martingale concentration and regularized low-rank matrix regression.
result Establishes always-valid risk bound process for online matrix completion.
New guarantees for matrix completion from any deterministic sampling patterns.
problem Proving guarantees for low-rank matrix completion from non-random sampling schemes.
method Introduced a graph with observed entries as edges to analyze the performance of constrained nuclear norm minimization algorithm.
result The algorithm can successfully complete the matrix if the observation graph is well-connected and has similar node degrees.
We describe several algorithms for matrix completion and matrix approximation when only some of its entries are known. The approximation constraint can be any whose approximated solution is known for the full matrix. For low rank approximations, similar algorithms appears recently in the literature under different name…
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…
New algorithm reduces policy regret in tallying bandits.
problem Measuring online learning performance against adaptive adversaries.
method Tallying bandit model, efficient algorithm with complete policy regret guarantee.
result Achieves a complete policy regret guarantee of .
This paper addresses the problem of low-rank distance matrix completion. This problem amounts to recover the missing entries of a distance matrix when the dimension of the data embedding space is possibly unknown but small compared to the number of considered data points. The focus is on high-dimensional problems. We r…
Study compares LRMC algorithms under dependent sampling in various applications.
problem Recovering missing entries in partially observed low-rank matrices with dependent sampling.
method Various LRMC algorithms tested under dependent sampling in different contexts.
result Performance differences among LRMC algorithms under dependent sampling.
Two algorithms estimate Wasserstein distance matrices from few entries for manifold learning.
problem Estimating Wasserstein distance matrices from limited data for manifold learning.
method Proposes two algorithms: matrix completion and Nyström completion for square Wasserstein matrices.
result Nyström completion can outperform matrix completion with a fixed sample budget and improve classification stability.
We consider general Morse-Smale diffeomorphisms on a closed orientable two-dimentional surface. In this paper it is proved that the complete topological invariant of Morse-Smale diffeomorphisms is finite, the algorithm of the construction of the complete topological invariant in explicit form is given and necessary and…
The paper improves tensor completion bounds using spectral gap.
problem Theoretical limitations in tensor completion, especially for deterministic sampling.
method Bounding the generalization error of tensor completion methods using spectral gap.
result Improved bounds on tensor completion error, reducing rank dependence.