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