Online Orthogonal Matching Pursuit
- Others:
- Statistique mathématique et apprentissage (CELESTE) ; Inria Saclay - Ile de France ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de Mathématiques d'Orsay (LMO) ; Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)
- Laboratoire de Mathématiques d'Orsay (LMO) ; Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)
- Understanding the Shape of Data (DATASHAPE) ; Inria Sophia Antipolis - Méditerranée (CRISAM) ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Inria Saclay - Ile de France ; Institut National de Recherche en Informatique et en Automatique (Inria)
- ANR-19-CHIA-0021,BISCOTTE,Approches statistiquement et computationnellement efficicaces pour l'intelligence artificielle(2019)
Description
Greedy algorithms for feature selection are widely used for recovering sparse high-dimensional vectors in linear models. In classical procedures, the main emphasis was put on the sample complexity, with little or no consideration of the computation resources required. We present a novel online algorithm: Online Orthogonal Matching Pursuit (OOMP) for online support recovery in the random design setting of sparse linear regression. Our procedure selects features sequentially, alternating between allocation of samples only as needed to candidate features, and optimization over the selected set of variables to estimate the regression coefficients. Theoretical guarantees about the output of this algorithm are proven and its computational complexity is analysed.
Additional details
- URL
- https://hal.archives-ouvertes.fr/hal-03141061
- URN
- urn:oai:HAL:hal-03141061v1
- Origin repository
- UNICA