Random Projections on Smooth Manifolds

Random Projections on Smooth Manifolds

Random Projections on Smooth Manifolds -A short summary RG Baraniuk, MK Wakin Foundations of Computational Mathematics Presented to the University of Arizona Computational Sensing Journal Club Presented by Phillip K Poon Optical Computing and Processing Laboratory The Motivation\Problem The Goal: Dimensionality Reduction Extract low dimensional information from a signal that is in a high dimensional space Preserve critical relationships among parts of the data

Understand the structure of the low dimensional information Applications: Compression Find a low dimensional representation from which the original high dimensional data can be reproduced General overview of dimensionality reduction Make a model (or estimate) of the expected behavior of the low dimensional information. These models often assume some structure to the low dimensional information

Ex. Given our data was presented as a cube our information probably lives on a line. Using the constraints and assumptions placed by the model, algorithms process the data into the desired low dimensional information Three common model classes Linear models Sparse models Manifold models Linear Models High dimensional data signal, depends linearly on a low dimensional set of

parameters. These models often uses a basis which allows the data, x, to be represented with a few coefficients, {1,2,,N} } i.e. A Fourier orthonormal basis High dimensional signal Low dimensional representation This results in a signal class, F = span({i} i ) , in a K-dimensional linear 2 subspace of RN} These classes of signals have a linear geometry which lead to linear algorithms for

dimensionality reduction Principal Component Analysis is the optimal linear algorithm N} on-adaptive technique requires training data Sparse (Nonlinear) Models Similar to linear models A few coefficients in the new basis represents/approximates the high dimensional data Unlike linear model, the relevant set of basis elements, may change from signal to signal N} o single low dimensional subspace suffices to represent all K-sparse signals Thus not closed under addition Thus N} OT a linear The set of sparse signals must be written as a non-linear union on distinct K

dimensional subspaces K := F = [ span ({i} i ) 2 Examples of situations requiring sparse models N} atural signals Audio recordings Images

Piecewise smooth signals [???] Information in signal encoded in the location and strength of each coefficient On the surface sparse signals seem to requires an adaptive and nonlinear technique!! Compressive Sensing and Sparse (Nonlinear) Models CS uses nonadaptive linear methods Encoder requires no prior knowledge of the signal Decoder uses the sparsity model to recover the signal Every K-sparse signal can be recovered high probability of success using M = O(K log (N} /K)) linear measurements, y = x is a measurement\encoding matrix drawn from random

distribution Random measurements allow for a universal or nonadaptive measurement scheme Invokes the Restricted Isometry Property of the measurement scheme: N} o two points are mapped to the same location in the new basis Similar to concept of injective mapping??? N} ew and explosive area of research! The Restricted Isometry Property Accurate recovery of sparse signals require a stable embedding when encoded N} o two points map to same location

Sparse signals remain well separated in RM A random measurement matrix obeying the RIP will guarantee accurate recovery Requires M = O(K log (N} /K)) The Johnson-Lindenstrauss Lemma Intimately connected to the RIP Manifold Models Classic example: The swiss roll Linear models like PCA or MDS would fail They only see the Euclidean straight line distance!

Even more we cant assume sparsity! Compressive sensing fail So manifold modeled signals are needed! A few terms: What is a manifold? Manifolds are very general shapes and structures. A surface is a 2 manifold A volume is a 3 manifold

Manifolds are locally Euclidean They seem flat if you look close enough! i.e. Earth looks flat! Any object that can be charted is a manifold Geodesic Distance: Shortest distance between points in curved space Manifold Models

May not be represented with a sparse set of coefficients More general than framework of bases Manifold models arise when we believe signal has as a continuous and often nonlinear dependence on some parameters. K-dimensional parameter carries relevant information The signal x 2 RN} changes as a continuous and nonlinear function of these parameters The geometry of the signal class forms a nonlinear K-dimensional submanifold of RN} , F = { x : 2 }

is a K-dimensional parameter space Manifold Learning Most manifold modeled signals require learning the manifold structure Learning involves constructing non-linear mappings from RN} to RM that is adapted from training data Mapping preserves a characteristic property of manifold A Classic Manifold Learning Technique: ISOMAP Seeks to preserve all the pair-wise

geodesic manifold distances! Approximates faraway distances by adding up the small interpoint distances through the shortest route Burden of storing sampled data points increases with native dimension N} of the data Each manifold learning algorithm attempts to preserve a different geometric property of the underlying manifold What does Random Projections on Manifolds do for us? Suggests that Compressive Sensing is not

limited only to sparse signals but also manifold modeled signals A provably small number of M random linear projections can preserve key information of the manifold-modeled signal N} o training N} on-adaptive Mapping to lower dimension is linear! Significantly reduced computation Random Projections Tells Us A Lot Manifold Learning algorithms try to preserve key properties of the manifold Random projections accurately approximate many properties of the manifold: Ambient and geodesic distances between all

point pairs Dimension of the manifold Topology, local neighborhoods, and local angles Lengths and curvature of paths on the manifold Volume of the manifold The punchline Like CS for sparse models, Random Projections for Manifold Models requires that the number of random linear projections, M, is linear in the information level K and logarithmic in ambient dimension N} . Allows for stable embedding under a random linear projection from the high to low dimensional submanifold. CS can be extended to sparse and manifold

signals! Conclusion Overview of Dimensionality Reduction Linear Models Sparse Models Manifold Models Manifold Learning Techniques Random Projections on Smooth Manifolds more efficient than learning and possibly extends CS to non sparse signals!

Recently Viewed Presentations

  • Seasonal Climate Outlook - semc.wa.gov.au

    Seasonal Climate Outlook - semc.wa.gov.au

    ACORN-SAT land area average. Upward trend clearly visible, but variability greater (because smaller amount of data). Warm years clustered in recent decades - although there were some earlier on. Cool years clustered in earlier decades - although still some recent.
  • 以上頷牙科植體作為長期藥物釋放與生醫感測裝置之前導性研究 A preliminary study on long-term ...

    以上頷牙科植體作為長期藥物釋放與生醫感測裝置之前導性研究 A preliminary study on long-term ...

    Intra-maxillary Drug delivery and Bio-sensing via Dental Implant and its considerations. Li, Yu-Jung . Lecturer of Anatomy, Physiology, and Pathology, St. Mary's Junior College of Medicine, Nursing, and Management,
  • Poster Template 76.2 cm x 106.68 cm (30"x42") - Cochrane

    Poster Template 76.2 cm x 106.68 cm (30"x42") - Cochrane

    153.4 days, 216 days, 3£338, 4£299, 5£376*Unlike the effectiveness data of this review, the included economic studies have not been weighted according to sample size; hence risk ratios (RR) of cost of relapse for the study population (if calculated) may...
  • Chapter 1

    Chapter 1

    Parsing Bottom-Up. The only complicated thing is reducing. 1. If the right hand side of the indicated production has k symbols, pop the top k things off the stack (that is, k state-symbol pairs). This is the handle.
  • Pointers, Pointers, Pointers CSE 333 Spring 2018

    Pointers, Pointers, Pointers CSE 333 Spring 2018

    Faking Call-By-Reference in C. Can use pointers to approximate call-by-reference. Callee still receives a . copy. of the pointer (i.e. call-by-value), but it can modify something in the caller's scope by dereferencing the pointer parameter
  • Session Title Session Subtitle

    Session Title Session Subtitle

    Dennis Wilson. Eastern Washington University. Business Intelligence. Coeur d'Alene, Idaho. NWEUG. 2015. ... You will learn how we use Banner and Data Mining tools to identify students at risk. Learn about factors that influence student retention. We will share our...
  • The Periodic Table - GST BOCES

    The Periodic Table - GST BOCES

    The Periodic Table Periodic Table of Elements There are 117 elements (January, 2007) Your table contains 113 94 of the elements are naturally occurring, the rest are man-made Most of the elements were discovered between 1735-1843 History/Development Development of the...
  • Designing Sustainable Landscapes for Avian Conservation in ...

    Designing Sustainable Landscapes for Avian Conservation in ...

    Designing Sustainable Landscapes for Avian Conservation in the SAMBI area. original graphic art by: Griffin Shreves III ... SLAMM Output for SAMBI DSL Utilizing A1FI Emission Scenario, Decadal Predictions 2000-2100 (ESRI GRID) ... Designing Sustainable Landscapes for Avian Conservation in...