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