Efficient Nonnegative Tensor Factorization via Saturating Coordinate
Descent
- URL: http://arxiv.org/abs/2003.03572v1
- Date: Sat, 7 Mar 2020 12:51:52 GMT
- Title: Efficient Nonnegative Tensor Factorization via Saturating Coordinate
Descent
- Authors: Thirunavukarasu Balasubramaniam, Richi Nayak, Chau Yuen
- Abstract summary: We propose a novel fast and efficient NTF algorithm using the element selection approach.
Empirical analysis reveals that the proposed algorithm is scalable in terms of tensor size, density, and rank.
- Score: 16.466065626950424
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: With the advancements in computing technology and web-based applications,
data is increasingly generated in multi-dimensional form. This data is usually
sparse due to the presence of a large number of users and fewer user
interactions. To deal with this, the Nonnegative Tensor Factorization (NTF)
based methods have been widely used. However existing factorization algorithms
are not suitable to process in all three conditions of size, density, and rank
of the tensor. Consequently, their applicability becomes limited. In this
paper, we propose a novel fast and efficient NTF algorithm using the element
selection approach. We calculate the element importance using Lipschitz
continuity and propose a saturation point based element selection method that
chooses a set of elements column-wise for updating to solve the optimization
problem. Empirical analysis reveals that the proposed algorithm is scalable in
terms of tensor size, density, and rank in comparison to the relevant
state-of-the-art algorithms.
Related papers
- Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms.
Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability.
We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
arXiv Detail & Related papers (2023-07-17T20:11:56Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications.
This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
arXiv Detail & Related papers (2023-01-30T15:46:39Z) - Fuzzy Clustering by Hyperbolic Smoothing [0.0]
We propose a novel method for building fuzzy clusters of large data sets, using a smoothing numerical approach.
The smoothing allows a conversion from a strongly non-differentiable problem into differentiable subproblems of optimization without constraints of low dimension.
arXiv Detail & Related papers (2022-07-09T12:40:46Z) - Alternating Mahalanobis Distance Minimization for Stable and Accurate CP
Decomposition [4.847980206213335]
We introduce a new formulation for deriving singular values and vectors of a tensor by considering the critical points of a function different from what is used in the previous work.
We show that a subsweep of this algorithm can achieve a superlinear convergence rate for exact CPD with known rank.
We then view the algorithm as optimizing a Mahalanobis distance with respect to each factor with ground metric dependent on the other factors.
arXiv Detail & Related papers (2022-04-14T19:56:36Z) - Infinite-Dimensional Sparse Learning in Linear System Identification [0.2867517731896504]
This paper proposes an infinite-dimensional sparse learning algorithm based on atomic norm regularization.
The difficulty in solving the problem lies in the fact that there are an infinite number of possible atomic models.
arXiv Detail & Related papers (2022-03-28T13:18:48Z) - Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
We study algorithms for estimating the statistical leverage scores of rectangular dense or sparse matrices of arbitrary rank.
Our approach is based on combining rank revealing methods with compositions of dense and sparse randomized dimensionality reduction transforms.
arXiv Detail & Related papers (2021-05-23T19:21:55Z) - Learned Block Iterative Shrinkage Thresholding Algorithm for
Photothermal Super Resolution Imaging [52.42007686600479]
We propose a learned block-sparse optimization approach using an iterative algorithm unfolded into a deep neural network.
We show the benefits of using a learned block iterative shrinkage thresholding algorithm that is able to learn the choice of regularization parameters.
arXiv Detail & Related papers (2020-12-07T09:27:16Z) - On Application of Block Kaczmarz Methods in Matrix Factorization [2.335152769484957]
We discuss a block Kaczmarz solver that replaces the least-squares subroutine in the common alternating scheme for matrix factorization.
We find block sizes that produce a solution comparable to that of the least-squares solver for only a fraction of the runtime and working memory requirement.
arXiv Detail & Related papers (2020-10-20T21:29:50Z) - Columnwise Element Selection for Computationally Efficient Nonnegative
Coupled Matrix Tensor Factorization [16.466065626950424]
Nonnegative CMTF (N-CMTF) has been employed in many applications for identifying latent patterns, prediction, and recommendation.
In this paper, a computationally efficient N-CMTF factorization algorithm is presented based on the column-wise element selection, preventing frequent gradient updates.
arXiv Detail & Related papers (2020-03-07T03:34:53Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
This class of algorithms encompasses several randomized methods among the fastest solvers for least-squares problems.
We focus on two classical embeddings, namely, Gaussian projections and subsampled Hadamard transforms.
Our resulting algorithm yields the best complexity known for solving least-squares problems with no condition number dependence.
arXiv Detail & Related papers (2020-02-21T17:45:32Z) - Differentiable Top-k Operator with Optimal Transport [135.36099648554054]
The SOFT top-k operator approximates the output of the top-k operation as the solution of an Entropic Optimal Transport (EOT) problem.
We apply the proposed operator to the k-nearest neighbors and beam search algorithms, and demonstrate improved performance.
arXiv Detail & Related papers (2020-02-16T04:57:52Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.