Rice Univesrity Logo
    • FAQ
    • Deposit your work
    • Login
    View Item 
    •   Rice Scholarship Home
    • Faculty & Staff Research
    • George R. Brown School of Engineering
    • Electrical and Computer Engineering
    • ECE Publications
    • View Item
    •   Rice Scholarship Home
    • Faculty & Staff Research
    • George R. Brown School of Engineering
    • Electrical and Computer Engineering
    • ECE Publications
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Random Projections of Smooth Manifolds

    Thumbnail
    Name:
    Bar2006Oct1RandomProj.PDF
    Size:
    239.6Kb
    Format:
    PDF
    View/Open
    Author
    Baraniuk, Richard G.; Wakin, Michael
    Date
    2006-10-01
    Abstract
    Many types of data and information can be described by concise models that suggest each data vector (or signal) actually has â few degrees of freedomâ relative to its size N. This is the motivation for a variety of dimensionality reduction techniques for data processing that attempt to reduce or eliminate the impact of the ambient dimension N on computational or storage requirements. As an example, many signals can be expressed as a sparse linear combination of elements from some dictionary. The sparsity of the representation directly reflects the conciseness of the model and permits efficient techniques such as Compressed Sensing (CS), an emerging theory for sparse signal recovery requiring only a small number of nonadaptive, random linear measurements. In other cases, the conciseness of the signal model may dictate that the signal class forms a low-dimensional manifold as a subset of the high-dimensional ambient space R^N. This type of geometric structure may not be neatly reflected in a sparse representation. Instead, dimensionality reduction techniques for manifold-modeled data typically involve â learningâ the manifold structure from a collection of data points, often by constructing nonlinear mappings from R^N to R^M for some M < N that are adapted to the training data and intended to preserve some characteristic property of the manifold. In this paper, we propose a new approach for nonadaptive dimensionality reduction of manifold-modeled data, demonstrating that a small number of random linear projections can preserve key information about a manifold-modeled signal. We center our analysis on the effect of a random linear projection operator Phi: R^N -> R^M on a smooth K-dimensional submanifold F of R^N. As our main theoretical contribution, we establish a sufficient number M of random projections to guarantee that, with high probability, all pairwise Euclidean and geodesic distances between points on F are well-preserved under the mapping Phi. Our results bear strong resemblance to CS. As in CS, the random measurements we propose can be used to recover the original data in R^N. Moreover, like the fundamental bound in CS, our requisite M is linear in the â information levelâ K and logarithmic in the ambient dimension N; we also identify a logarithmic dependence on the volume and curvature of the manifold. In addition to recovering faithful approximations to manifold-modeled signals, however, the random projections we propose can also be used to discern key properties about the manifold. We discuss connections with existing techniques in manifold learning.
    Description
    Journal Paper
    Citation
    R. G. Baraniuk and M. Wakin, "Random Projections of Smooth Manifolds," 2006.
    Published Version
    http://dx.doi.org/10.1007/s10208-007-9011-z
    Keyword
    Manifolds; dimensionality reduction; random projections; Compressed Sensing; sparsity; More... manifold learning; Johnson-Lindenstrauss lemma; Multiscale geometry processing; Manifolds; dimensionality reduction; random projections; Compressed Sensing; sparsity; manifold learning; Johnson-Lindenstrauss lemma Less...
    Type
    Journal article
    Citable link to this page
    https://hdl.handle.net/1911/19724
    Metadata
    Show full item record
    Collections
    • DSP Publications [508]
    • ECE Publications [1468]

    Home | FAQ | Contact Us | Privacy Notice | Accessibility Statement
    Managed by the Digital Scholarship Services at Fondren Library, Rice University
    Physical Address: 6100 Main Street, Houston, Texas 77005
    Mailing Address: MS-44, P.O.BOX 1892, Houston, Texas 77251-1892
    Site Map

     

    Searching scope

    Browse

    Entire ArchiveCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsTypeThis CollectionBy Issue DateAuthorsTitlesSubjectsType

    My Account

    Login

    Statistics

    View Usage Statistics

    Home | FAQ | Contact Us | Privacy Notice | Accessibility Statement
    Managed by the Digital Scholarship Services at Fondren Library, Rice University
    Physical Address: 6100 Main Street, Houston, Texas 77005
    Mailing Address: MS-44, P.O.BOX 1892, Houston, Texas 77251-1892
    Site Map