Publication

Optimization Convergence of Matching Pursuit Algorithms

2017

Résumé

The matching pursuit algorithm and its variants are among the most commonly used methods for greedy optimization. In this paper, we present the first explicit convergence rates of matching pursuit methods in an optimization sense, for general sets of atoms. We present sublinear O(1/t) convergence on general smooth objectives, and linear convergence on strongly convex objectives. Our algorithm variants and rates do not need any incoherence or sparsity assumptions. Direct applications of the presented algorithms are structured matrix and tensor factorization problems.

Source officielle

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

2017

Résumé

Source officielle

Concepts associés (31)

Sparse approximation

Sparse approximation (also known as sparse representation) theory deals with sparse solutions for systems of linear equations. Techniques for finding these solutions and exploiting them in applications have found wide use in , signal processing, machine learning, medical imaging, and more. Consider a linear system of equations , where is an underdetermined matrix and . The matrix (typically assumed to be full-rank) is referred to as the dictionary, and is a signal of interest.

Matching pursuit

Matching pursuit (MP) is a sparse approximation algorithm which finds the "best matching" projections of multidimensional data onto the span of an over-complete (i.e., redundant) dictionary . The basic idea is to approximately represent a signal from Hilbert space as a weighted sum of finitely many functions (called atoms) taken from . An approximation with atoms has the form where is the th column of the matrix and is the scalar weighting factor (amplitude) for the atom . Normally, not every atom in will be used in this sum.

Sparse dictionary learning

Sparse dictionary learning (also known as sparse coding or SDL) is a representation learning method which aims at finding a sparse representation of the input data in the form of a linear combination of basic elements as well as those basic elements themselves. These elements are called atoms and they compose a dictionary. Atoms in the dictionary are not required to be orthogonal, and they may be an over-complete spanning set. This problem setup also allows the dimensionality of the signals being represented to be higher than the one of the signals being observed.

Afficher plus

Publications associées (32)

Afficher plus

Optimization Convergence of Matching Pursuit Algorithms

Chattez avec Graph Search

Optimization in Modern Machine Learning: Steepest Descent Theory and Trustworthy Models

Training Dynamics of Gradient Methods on Simple Neural Architectures

A \({(2+\varepsilon )}\)-Approximation Algorithm for Metric \({k}\)-Median