i'm does to mix an i'm from the uh program in and computational mathematics to prince university uh i'm rubber colour makes do that and so i'm gonna be talking about some work i did this past summer with chris when uh grad student at urbana champaign and is adviser negative about and also map fig is that the air force since to tech not so first we'll talk about the problem at hand a see i have a file but don't wanna share with a bunch of my friends um but i wanna be able to determine if any of my friends and decide to a week this file to other people so let's say i notice uh one the copies of the files in the wrong person hands i can look at back copy and notice if i had put a finger a distinct fingerprint on that notice where the fingerprint came from and uh identify might trader now let's suppose that my friends are smarter and uh a group of them a group of corporate just side to collaborate and make a forgery with their copies um that's gonna make it harder for me to identify with the traders are um but let's say the way they for it is they do it convex combination of their copies then the ad some random noise on top of that well my goal also identify the corporate and the talk is uh geared dance sits question of how you do that so the first thing you might do is isolate the noisy combination a fingerprints you take the forgery in use subtract off the host signal and uh what's left is a convex combination of fingerprints plus some noise um if you view your fingerprints as columns of a short fat matrix uh big F multiply that by out of uh which has mostly zero entries um a nonzero entries are the alpha case K being in a coalition script K you plus this uh this apps on vector when you pose it in this matrix vector format you basically want to recover the support of L for that the locations of the nonzero entries of alpha given the measurements so you have uh why mine assess equal this F L for plus epsilon so what's first look at the noiseless case where epsilon is zero then you have this this picked two all uh figure of the matrix vector uh thing the thing on the left is what we have available to us it's the forgery my as the host signal the short fat matrix the columns are uh fingerprints and then the sparse vector on the right there is alpha the white entries trees are the zero entries in the colour trees are the uh the alpha case in our convex combination so when we pose a problem this way uh it's appropriate to consider uh compressed sensing as a uh solution alternative um what compressed sensing offers is machinery that allow us to not only identify the support of alpha but actually recover uh with its uh the values of the nonzero entries uh but this assumes uh sparsity in the support that the there's not too many colluders in the coalition um so if we assume that are coalition is small enough uh we will be able to use uh compressed sensing ideas to find the the perpetrators um so to go a little more in depth on but machinery offered by compressed sensing let's talk about the restricted isometry property this is a property on short fat matrices that's says that the short that matrix F axes and new ice on a tree on a sufficiently sparse vectors so if you're vector X has uh no more than K nonzero entries them the length of uh F fax is some between one minus delta to one plus delta times that like the backs square um and and the importance of the research price on tree property as reflecting this that's and by as and tao which states that if you're matrix is alright P then you can find any case sparse vector X by minimizing the one norm overall vectors that map to F that normally you have to find the sparse as vector uh in the pre-image but because are short fat matrix satisfies all right P were able to you this problem as being equivalent to this a one minimisation uh which we can solve by when you're programming so the moral this slide is uh if your fingerprints R columns in or i P matrix then you can find alpha and identify perpetrators in the noiseless case i just using linear programming uh but we didn't assume and noiseless case we assume noise so let's talk about the noise um so the results on uh linear programming to a perform uh this recovery problem uh and there's count limited if epsilon is small then you can perform linear programming and but only work if epsilon a small uh so let's start walking away from when you're programming because we care about noise um what's look at focused detection where we care whether a particular user is in the cooler so look at the set of all fingerprint combinations where the weights are equal and the coalition size is no more think K and break that's set up into a set in which i is a member of the coalition and M is not measure uh member the coalition so gives you the guilty that for um and the not guilty set for and and we can talk about the distance between these two sets is being the minimum distance between points and one set another set we can actually bound this distance ah from below uh provided the fingerprints come from columns of an P matrix um and so this really illustrates uh but there is some resilience to noise with uh with a P fingerprint but there is a if provided the noise is have this lower bound you'll be able to determine whether uh a a given user is guilty so or P appears to be a great for fingerprint design so how do we build an nor P matrix um the typical construction uses random entries if all the entries are independently drawn gaussian random variables then the resulting matrix is alright P with high probability at it's only with high probability there is some probability that you'll fail but you want know it because tracking that a matrix satisfies all P is hard so this we just uh look for deterministic constructions uh are right P matrices and the key tool and doing this is using what's called the group in circle theorem which states that well a diagonal matrix the eigenvalues are the diagonal entries well nearly diagonal matrix the diagonal entries will be close to the eigenvalues uh how close well well B turn and by the size of the off diagonal entries so when trying to demonstrate that a matrix as R right P you're really trying to say something that the eigenvalues of all the submatrices of the grammy and so if you take uh you take your matrix of fingerprints the seem your fingerprints have unit norm to find the worst-case case here is to be the size of the largest inner product between the fingerprint and then for each day we can analyse with the small the delta is for which that is K don't alright P the way you do that is you want to find out how far away from one the eigenvalues of each of the sub matrices are so you subtract the sub grant yeah uh you subtract a uh the identity from the sub gram yeah which centres it about zero as opposed to centring about one and then the maximum distance will be the spectral norm of this differ and using the group square the group score in circle there uh this we bounded above by K minus one times me why because there's K minus one off diagonal entries in each row and new is the size of a large off the act one tree so i just demonstrated to you the a that F is "'kay" don't to alright P whenever dealt is bigger then "'kay" minus one times the worst-case case yeah it would be nice if the worst-case coherence or small because that would give us the best are ap P parameter uh for utility um how small can the worst-case coherence parents be the welch bound tells us that the worst case coherence is bounded below by this square root and there exist constructions which actually achieve this lower bow those are called a query angular tight frame so for echo wearing are tight frames new is equal to this well spent on the square root and so using that quality and the inequality from a previous slide we know the X wing are tight frames are actually K dealt or P when you satisfy this inequality one delta square is bigger than uh this quotient because echoing coming tight frames happened to achieve the welsh bound and because the worst-case coherence is what naturally comes out of the gross an argument to demonstrate a right P echoing are tight frames happen to be a the state-of-the-art for deterministic alright Q construction and it's relatively easy to build and that crank type frame i read a paper recently with matt fig guess called steiner at winning tight frames if you google stack steiner T S they'll so you had a how to construct these guys but i'm not gonna talk about that today i just one leave us uh fact that i wing are tight frames appear to be particularly well suited as uh a fingerprint codes both because there or P and because they're deterministic easy the easy to build so what's zoom in on this particular subclass of a right P matrices in the context of focused detection so with focused detection we take are noisy a convex combination a fingerprints and we compare to all the fingerprints and our dictionary the fingerprints that looks the most like or noisy combination we uh we say belong to guilty suspects so this process in certain false positive and false negative probability and uh the probability uh the fact that there's a probability a talk about is because epsilon is uh modelled as a and with variance signals squared so the false positive probability is the probability that we declare that he's a guilty when is actually not and vice versa for a some negative well i'm gonna talk about is the the worst case of these types of probable so the worst-case case false positive is for each uh coalition you look at all guys not your coalition take the maximum uh false positive probability and maximise all over all of the coalition's but for the E false negative uh it's a different story because we we want to catch at least one colluder namely the most vulnerable so instead of maximizing over all a members of the coalition we actually minimize uh the false negative probabilities over all members of coalition the maximise that over all oh cool ish so it's so with these we uh we actually have a result that says fingerprints that form an knack wearing tight frame actually have these false positive and false negative probabilities satisfy these these uh inequalities using the Q function and uh i like to just go over the use any qualities and more detail the first one an upper bound on a false positive it independent of the colluders choice of alpha so remember alpha is the weights that they uh that they chose to um use for their convex combination of fingerprints for the forgery regardless of what coefficients they use they won't be able to frame and in is that user sense this upper bound is and the kind of health a so that that's kind of a fun interpretation and then the second equality uh we notice that the upper bound is maximised when the coefficients in the collusion or equal so the way we interpret this is that uh the colluders well they don't wanna get caught they have the best chance of not getting caught under focus detection if there if their weights are equal and this comes out of the fact that focused detection is seeking to find the uh the most vulnerable so one the weights are equal the most vulnerable as least normal so this talk was basically a um a presentation selling compressed sensing for uh think print design a a compressed sensing ideas like with the restricted isometry property appear be useful in figure fingerprint design and and uh i think of ways of identifying corporate and equating wearing tight frames being deterministic and uh a right P easy to construct there uh there well suited for fingerprint in designing them focus detection uh appears to work well and i'd like to think more about different ways of detecting technical using equating or type frame fingerprint this concludes my talk all a chain the questions of this we have time for questions oh in compressed sensing you want to work can sort the ones you brought the young vector where are here did you want to sit in just catching one colluder so the can and mismatch between right so um another um another thing that i could do is instead of just catching the most vulnerable i could catch the the top cable able um or uh when i set up the focus detection i set a threshold tao and decide that a user is guilty if the test cystic uh exceeds town um i don't necessarily i will necessarily have only one guilty suspects with that uh with that process but with the uh the theorem state that i gave it it was based on uh uh most of all able the worst case scenario now uh if you can only get one but agreed compressed sensing is more uh more versatile it's it's intended to capture the entire support recover the entire vector it tired so um there's definitely more work to be done to to incorporate a compressed sensing ideas and model selection ideas for uh for the fingerprints problem great i um i don't see the um i did you did you could this seeing the difference with preview paper from the same or for like yeah um the one based on simplex exclude or or its because it seemed like school because the set ups in to be the same the detectors a linear your correlation so yeah uh uh make are published a saying that simplex codes are them all provided the number of users is that most uh the signal the mentioned plus one and the U D of this solution is that were allowed to have uh the number of users not be so construct it can be a larger than and plus one and that's what uh equating english tight frames uh allows for in fact uh constructions exist ah for a number of users uh scaling on the order of the square of the signal dimension so that's much more uh versatility band what the simplex good you have and no be more specific simplex codes happen to be a special case uh a query were tight frames so um so i'm glad you mention that it really uh kind of puts this work in like proper context oh the questions do so thank you know match for