Stable recovery of sparse vectors from random sinusoidal feature maps

Mohammadreza Soltani, Chinmay Hegde

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    Random sinusoidal features are a popular approach for speeding up kernel-based inference in large datasets. Prior to the inference stage, the approach suggests performing dimensionality reduction by first multiplying each data vector by a random Gaussian matrix, and then computing an element-wise sinusoid. Theoretical analysis shows that collecting a sufficient number of such features can be reliably used for subsequent inference in kernel classification and regression. In this work, we demonstrate that with a mild increase in the dimension of the embedding, it is also possible to reconstruct the data vector from such random sinusoidal features, provided that the underlying data is sparse enough. In particular, we propose a numerically stable algorithm for reconstructing the data vector given the nonlinear features, and analyze its sample complexity. Our algorithm can be extended to other types of structured inverse problems, such as demixing a pair of sparse (but incoherent) vectors. We support the efficacy of our approach via numerical experiments.

    Original languageEnglish (US)
    Title of host publication2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 - Proceedings
    PublisherInstitute of Electrical and Electronics Engineers Inc.
    Pages6384-6388
    Number of pages5
    ISBN (Electronic)9781509041176
    DOIs
    StatePublished - Jun 16 2017
    Event2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 - New Orleans, United States
    Duration: Mar 5 2017Mar 9 2017

    Publication series

    NameICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
    ISSN (Print)1520-6149

    Other

    Other2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017
    Country/TerritoryUnited States
    CityNew Orleans
    Period3/5/173/9/17

    Keywords

    • nonlinear recovery
    • random features
    • sparsity

    ASJC Scopus subject areas

    • Software
    • Signal Processing
    • Electrical and Electronic Engineering

    Fingerprint

    Dive into the research topics of 'Stable recovery of sparse vectors from random sinusoidal feature maps'. Together they form a unique fingerprint.

    Cite this