Dictionary Learning Using Rank-One Atomic Decomposition (ROAD)

• URL: http://arxiv.org/abs/2110.12786v2
• Date: Tue, 26 Oct 2021 14:12:13 GMT
• Title: Dictionary Learning Using Rank-One Atomic Decomposition (ROAD)
• Authors: Cheng Cheng and Wei Dai
• Abstract summary: Dictionary learning aims at seeking a dictionary under which the training data can be sparsely represented. Road outperforms other benchmark algorithms for both synthetic data and real data.
• Score: 6.367823813868024
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Dictionary learning aims at seeking a dictionary under which the training data can be sparsely represented. Methods in the literature typically formulate the dictionary learning problem as an optimization w.r.t. two variables, i.e., dictionary and sparse coefficients, and solve it by alternating between two stages: sparse coding and dictionary update. The key contribution of this work is a Rank-One Atomic Decomposition (ROAD) formulation where dictionary learning is cast as an optimization w.r.t. a single variable which is a set of rank one matrices. The resulting algorithm is hence single-stage. Compared with two-stage algorithms, ROAD minimizes the sparsity of the coefficients whilst keeping the data consistency constraint throughout the whole learning process. An alternating direction method of multipliers (ADMM) is derived to solve the optimization problem and the lower bound of the penalty parameter is computed to guarantees a global convergence despite non-convexity of the optimization formulation. From practical point of view, ROAD reduces the number of tuning parameters required in other benchmark algorithms. Numerical tests demonstrate that ROAD outperforms other benchmark algorithms for both synthetic data and real data, especially when the number of training samples is small.

Related papers

• Faster WIND: Accelerating Iterative Best-of-$N$ Distillation for LLM Alignment [81.84950252537618]
  This paper reveals a unified game-theoretic connection between iterative BOND and self-play alignment. We establish a novel framework, WIN rate Dominance (WIND), with a series of efficient algorithms for regularized win rate dominance optimization.
  arXiv  Detail & Related papers  (2024-10-28T04:47:39Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  Trust-region (TR) and adaptive regularization using cubics have proven to have some very appealing theoretical properties. We show that TR and ARC methods can simultaneously provide inexact computations of the Hessian, gradient, and function values.
  arXiv  Detail & Related papers  (2023-10-18T10:29:58Z)
• Convergence of alternating minimisation algorithms for dictionary learning [4.5687771576879594]
  We derive sufficient conditions for the convergence of two popular alternating minimisation algorithms for dictionary learning. We show that given a well-behaved initialisation that is either within distance at most $1/log(K)$ to the generating dictionary or has a special structure ensuring that each element of the initialisation only points to one generating element, both algorithms will converge with geometric convergence rate to the generating dictionary.
  arXiv  Detail & Related papers  (2023-04-04T12:58:47Z)
• Simple Alternating Minimization Provably Solves Complete Dictionary Learning [13.056764072568749]
  This paper focuses on complete dictionary problem, where the goal is to reparametrize a set of given signals as linear combinations of atoms from a learned dictionary. There are two main challenges faced by theoretical and practical dictionary learning: the lack of theoretical guarantees for practically-used algorithms, and poor scalability when dealing with huge-scale datasets.
  arXiv  Detail & Related papers  (2022-10-23T18:30:45Z)
• Asymmetric Scalable Cross-modal Hashing [51.309905690367835]
  Cross-modal hashing is a successful method to solve large-scale multimedia retrieval issue. We propose a novel Asymmetric Scalable Cross-Modal Hashing (ASCMH) to address these issues. Our ASCMH outperforms the state-of-the-art cross-modal hashing methods in terms of accuracy and efficiency.
  arXiv  Detail & Related papers  (2022-07-26T04:38:47Z)
• Discriminative Dictionary Learning based on Statistical Methods [0.0]
  Sparse Representation (SR) of signals or data has a well founded theory with rigorous mathematical error bounds and proofs. Training dictionaries such that they represent each class of signals with minimal loss is called Dictionary Learning (DL) MOD and K-SVD have been successfully used in reconstruction based applications in image processing like image "denoising", "inpainting"
  arXiv  Detail & Related papers  (2021-11-17T10:45:10Z)
• Dictionary Learning with Convex Update (ROMD) [6.367823813868024]
  We propose a new type of dictionary learning algorithm called ROMD. ROMD updates the whole dictionary at a time using convex matrices. The advantages hence include both guarantees for dictionary update and faster of the whole dictionary learning.
  arXiv  Detail & Related papers  (2021-10-13T11:14:38Z)
• SreaMRAK a Streaming Multi-Resolution Adaptive Kernel Algorithm [60.61943386819384]
  Existing implementations of KRR require that all the data is stored in the main memory. We propose StreaMRAK - a streaming version of KRR. We present a showcase study on two synthetic problems and the prediction of the trajectory of a double pendulum.
  arXiv  Detail & Related papers  (2021-08-23T21:03:09Z)
• 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)
• Efficient Sparse Coding using Hierarchical Riemannian Pursuit [2.4087148947930634]
  Sparse coding is a class of unsupervised methods for learning a representation of the input data in the form of a linear combination of a dictionary and a code. We propose an efficient synthetic state scheme for sparse coding tasks with a complete dictionary.
  arXiv  Detail & Related papers  (2021-04-21T02:16:44Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  We propose two single-timescale single-loop algorithms that require only one data point each step. Our results are expressed in a form of simultaneous primal and dual side convergence.
  arXiv  Detail & Related papers  (2020-08-23T20:36:49Z)

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.