### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# ADV TOPS IN SIGNAL PRO EE 639

UK

GPA 3.81

### View Full Document

## 25

## 0

## Popular in Course

## Popular in Electrical Engineering

This 24 page Class Notes was uploaded by Adaline Pollich on Friday October 23, 2015. The Class Notes belongs to EE 639 at University of Kentucky taught by Ching Cheung in Fall. Since its upload, it has received 25 views. For similar materials see /class/228317/ee-639-university-of-kentucky in Electrical Engineering at University of Kentucky.

## Reviews for ADV TOPS IN SIGNAL PRO

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/23/15

Multimedia Information Systems Samson Cheun g EE 639 Fall 2004 Lecture 22 Dimension Reduction Distance Preserving Mapping Outline I Problem Statement and Challenges I Worstcase bounds I Optimizationbased methods I Global Multidimensional Scaling I Local ISOMAP Local Linear Embedding LLE I Methods fJOr similarity search I Fastmap I Triangular Inequality Pruning Challenges So far we have only talk about how to reduce the dimension of finite dimensional vectors What about if the vectors have no 39or infinite dimension Examples Timeseries Data 5 Probability Density Function 5 Graphs Typically all we have is a metric dxy39 that measures the dissimilarity betWeen x and y Problem of embedding how to map x into a lowdimensional feature space usually l12 or Lo with distance relationship preserved Net al metre Can be preeerved a Not all metric can be preserved no matter how high the dimension of the feature space 3 Example Simple graph metric dxy distance of the shortest path There can only be one point C in any dimensional Euclidean Space with dCA dCB 05dAB ID What is the best we can do n Define Distortion D of a mapping ldx ixJ IPTxi5TxJi dx x 1 J D T maX1siltjsN m Bourgain 85 shows that given the pairwise metric distances any metric among a set of N points the distortion of em bedding them into a 1 space is 010g2N m This bound is tight there are examples that cannot achieve any better distortion 39 a Linial London and Rabinovich 94 gives a polynomialtime randomized algorithm to achieve this bound with dimension 390log2N2 y Usually better in practice most real life data are not too far from P Ii Inspire the use of random projection techniques meneiena 1 Problem Given distances dijdxxj among n data points x1x2xn find n pdimensional data points y1y2yn that whose 11 distances minimize some cost function 1 Typical cost functions m Square differences 21Zimclxi262 171Txi2Txi22 D Stress dxi3xjZPTxi 3Txj ji1 21 qu39 39 xi 2 m Example Given NN12 distance measurements dil Fix the feature space say 2D Euclidean Formulate the target cost function r 2 fy11ay12y21y22olea yN2 yi1 yj12 312 yJ22 iltj Use your favorite algorithms gradient descent hill climbing coordinate descent to solve the following minimization algorithm Inn13413212y21ay22yN1aJN2 f QR t 33 1 l t 115 r V Recover inner product matrix B from distances Force 0 5 yl yjTy yji yfyl 2yTyj yJTyj BU yy 2 211611341 Note that B YTY with Y y1 y2 yN is a symmetric matrix with rank p why Recover the coordinates from B B VIVT is the eigendecomposition where A has p non zero real eigenvalues Retaining only the nonzero eigenvalues we have B Vquotl VquotT If B is semipositive definite then Y V A V2 Comment about 1 It is a dual of PCA because PCA performs ei en decomposition on the covariance matrix YY which have the same set of nonzero eigenvalues as the inner product matrix YTY If B is not positive definite CS can still be used as long as the negative eigenvalues are much smaller than the positive ones If negative 39eigenvalues are big then one need to directly compute 39Y based on minimizing one of the cost functions typically using gradient descent starting with a partial solution obtained by CS Pmblem with MDS D Cares about all pairwise distancesi sacri ce local geometry for glObal donSis tenCe 3 Maybe better to enforcerlocal distanceand discard global structure local manifold embedding Two points may be closadin the high dim ensional 39sp ace but very far in terms oftheund rlying 39 structure geodesic distance Tenenbawim zoom Define neighborhood of each data point by its sbalrl Build a graph with an edge of weight wdxiixj39 between xi and xj if xi and xj are neighbors Geodesic distance between ANY xi and xj idGltxi x1 ZeeShOrtest pathin39G between x and X a Apply classical scaling on the geodesic distances Lacey Linear Embedding Revues and 8an For each data point x compute a linear approximation based on its k nearest neighbors can also be done based on distances only similar to CS quot Java Minimize With respect to yi for the computed wij JENU this turns out to be an eigenvalue problem as well because the above is a quadratic form Of a semi positive matrix l SOMAP Comparson to LLE 1 Similarities Preserve intrinsic geometry of data by computing local measUres rafter which data can be discarded Iil Somewhat arbitrary preprocessing rules to identify neighbors Both techniques require dense sampling of manifolds Difference in local measure 11 Geodesic distance vs neighborhood relatiOnship 1 Differences in application III ISOIVIAP more robust to outliers ISOIVIAP preserves distance LLE angles a LLE avoids complexity of pairwise distance computation warty eareh m The computations of MDS lSiOMAP LLE all require identification of nearby points 1 But if We Can do that we have solved the similarity search problem a Solutions a Incrementally build very interesting but don t know how to do a Train it on a small set and hope it generalize Other lowcomplexity embedding techniques Generic Multimedia Indexing Approach GEMINI Faloutsos 96 Original Space dxy LOWD Space d TxTV Feature Extraction Px Candidate set To prevent loss in recall we want xdqueryxlt to be a subset of x2d TqueryTxlta I If a 5 this implies d TxTySdxy This is called the contractive property and is a very desirable property If contractiveness is guaranteed then there is a possibility of loss in recall I Need to quantify the loss over the complexity reduction Festmep Fatwteoe e5 a Psuedoprojections on axes formed by pivot pomts xIo and x q X Xp Projx a By cosine law dXqX2dXpX2 dXpXq22y39dXpXq Projection Projy dxpx39239idxpxq2dxqx22dxpxq For the next dimension define new distance d Xy2 dXy2 DFOJXDFOJY2 and repeat the process Il W pvt Faloutsos argued that it makes sense to pick points that are far apart pseudo PCA How to efficiently find points that are far apart 1 Randomly pick a point x 2 Find the point y in DB that maximizes dxy 3 Find the point z in DB that maximizes dyz 4 Repeat 2 and 3 a number of times Problem with Frastm ap if the underlying metric is non euclidean new distances may become negative which results in a noncontractive mapping V I7 quot F JL J I Q y f v D 1 x I l F 1 In m Basic Triangle inequality dX3dq3 S dgtltQ S dgtlt5dq3 Use mul riple seeds To ob rain TighTer39 bounds maxi ldX5i39dq13i S dXIQ 5 mini dX5idq13i I llhl lemme 4quot mmd f i m L Imifiixf i w Hfhnimmificm lfdlwgr39 ij1m Imemp img Tranle Inequaity Pruning TIP Dimension Reduction For each signature vector x compute Tx given by T x A dxquotvs1 dxs 2 dxsm Only the lower Similarity Search for q bound 5 sad quoti Remove x in the database that sati A wTXTCI max Idixsi dqsii gt A Identifyx that satisfy dxq S a in the remainder of the database A P Berman and LG Shapiro 1999 flexible image databasesystem for contentbased retrieval Computer Vision and Image Understanding 75 12 175195 Use both bound f r runing 10000 r39andom dxy Lower bound S 3 Accuracy 100 Pruning Am r 70 0 c 3 o o L Q 3 0 Produc r of Two bounds S 9 o o o 0 Accuracy 938 1393 quot1 12 39 Pruning Am r 99 T U upper39 bound Heuristic justificati Simple algebra d3939xq lt 8 31 upperbound lt e 2 tm inidqsi dxsi D Not a tight bound gt no performance guarantee E Neither the upper bound nor the product of bounds forms a metric for indexing Try Difference of square 2 39dX Sidqsil dxsidqsi 2 IZ between Tx and Tq where Tx dgtltsl2 dgtltsm2 Prepesed ieehr ique Cheunga Zahker Q3 ii For each signature vector x compute Tx given by T x gt dxss125 dx58225 dxsism2 2 Project each Tx into TX with PCA T Tx gt Tx Similarity Search for q t remove x in the database that satisfy 2T39XTq gt A Identify x that satisfy dxq S s in the remainder of the database Performance of Version 2 4D Feature Extraction 8 D Feature Extraction Amount of Pruning Amount of Pruning 1 Accuracy 230 Accuracy 230 feet en nte Xecm 55mm Average of 100 random qUer ies on a da rabase of 23206 en rr ies Pruning Time Refinement Time v Scheme Accuracy Sequen al histogam PCA 89 130 i 14 ms 401 i 75 ms 100 6730 i 35 ms Haar 92 152 i 13 ms 123 i 28 ms Fastmap 91 131 i 15 ms 75 i 11 ms Proposed 89 131 i 08 ms

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.