Publication

Optimization Convergence of Matching Pursuit Algorithms

2017

Abstract

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.

Official source

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

2017

Abstract

Official source

Related concepts (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.

Related publications (32)

Optimization Convergence of Matching Pursuit Algorithms

Chat with 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