extfieldsofstudy:
Computer Science
Mathematics

text:
Curves on Flat Tori and Analog Source-Channel Codes

In this paper we consider the problem of transmitting a continuous alphabet discrete-time source over an AWGN channel. We propose a constructive scheme based on a set of curves on the surface of a N-dimensional sphere. Our approach shows that the design of good codes for this communication problem is related to geometrical properties of spherical codes and projections of N-dimensional rectangular lattices. Theoretical comparisons with some previous works in terms of the mean square error as a function of the channel SNR as well as simulations are provided.

I. INTRODUCTION
The problem of designing good codes for a continuous alphabet source to be transmitted over a Gaussian channel with power constraint and bandwidth expansion can be viewed as the one of constructing curves in the Euclidean space of maximal length and such that its folds (or laps) are a good distance apart. When the channel noise is below a certain threshold, a bigger length essentially means a higher resolution when estimating the sent value. On the other hand, if the folds of the curve come too close, this threshold will be small and the mean squared error (mse) will be dominated by large errors as consequence of decoding to the wrong fold. Explicit constructions of curves for analog source-channel coding for bandwidth expansion were presented, for example, in [11] and [12]. For insights on the bandwidth reduction case we refer the reader to [5].
In this work, we consider spherical curves in the 2Ndimensional Euclidean space. We develop an extension of the construction presented in [11] to a set of curves on layers of flat tori. Our approach explores the geometrical properties of spherical codes and projections of N -dimensional lattices. In the scheme presented here, homogeneity and low decoding complexity properties were preserved from [11] whereas the total length can be meaningfully increased. Theoretical results as well as simulations show that our approach outperforms the previous ones in terms of the tradeoff between SNR and mean squared error. This paper is organized as follows: in Sections II and III, we introduce some mathematical/information-theoretical tools used in our approach. In Section IV we present a scheme to design piecewise homogeneous curves on the Euclidean sphere and describe the encoding/decoding process. In Section V we derive an extended version of the Lifting Construction [8] suitable to our problem and present some examples and length comparisons with some previous constructions. In Section VI we provide an analysis of the asymptotic behavior of the mse as a function of the channel SNR and in Section VII simulation results are exhibited.

II. COMMUNICATION FRAMEWORK
The communication system we consider here is illustrated below. The objective is to transmit an input real value x associated to the random variable X over a channel of dimension N with additive Gaussian noise and average power constraint. The encoder uses a bandwidth expansion mapping in order to encode x to a point s s s(x) ∈ R N respecting the constraint E [s s s(X)s s s(X) t ] ≤ P . The decoder recovers an estimatex for the sent value attempting to minimize the mean squared error (mse) E[(X −X) 2 ]. The source is assumed to have pdf with support [0, 1) and s s s([0, 1)) will be referred to as the signal locus. If s s s is a continuous mapping, then the signal locus is a curve in R N .
This communication model is carefully analyzed in [7,Ch. 4]. Given a radius ρ > 0, let E ρ denote the event { z z z < ρ}. The mse can be split into two terms such that: For high values of the SNR P/σ 2 , P (E c ρ ) ≈ 0 and the mse is well approximated by E[(X −X) 2 |E ρ ] (the goodness of the approximation depends on the SNR and ρ). In this case, called the low noise regime, it is possible to show [7] that: where p(x) is the pdf of the source. Most of the analysis in Section VI will be done under the low noise regime. If the arXiv:1302.4706v3 [cs.IT] 13 Jun 2013 source is uniform, then an optimal parametrization for s s s(x) yields where L is the curve length. A geometric picture of the possible effects of the noise on the estimated value is given by Figure 1. Under the low noise regime, all the calculations can be essentially done by approximating s s s(x) by its tangent line and the system will be described by Equation (2). However, this is not true for large errors. Decoding to the wrong fold of the curve yields a poor performance of the system. This suggests that our objective is to choose long curves with a large distance between its folds.
In our constructions, the signal locus will be a collection of curves in R N rather than a single curve (this can be viewed as a "piecewise continuous" curve). Our analysis is mainly focused on uniform sources, although the scheme can be easily adapted to any source with limited support and even to Gaussian sources, by means of a companding function [7], as shown in Section VII.

A. Flat Tori
The unit sphere S 2N −1 ⊂ R 2N can be foliated with flat tori [1], [10] as follows. For each unit vector c c c = (c 1 , c 2 , .., c N ) ∈ R N , c i > 0, and The N -periodic function Φ c c c is a local isometry on its image, the torus T c c c , a flat N -dimensional surface contained in the unit sphere S 2N −1 . The torus T c c c = Φ c c c (R N ) is also the image of the hyperbox: Note also that each vector of S 2N −1 belongs to one, and only one, of these flat tori if we also consider the degenerated cases where some c c c i may vanish. Thus we say that the family of flat tori T c c c and their degenerations, with c c c = (c 1 , c 2 , .., c N ), c c c = 1, c i ≥ 0, defined above is a foliation of the unit sphere of S 2N −1 ⊂ R 2N .
It can be shown (Proposition 1 in [10]) that the minimum distance between two points, one in each flat torus T b b b and T c c c , is The distance between two points on the same torus T c c c , given by is bounded in terms of u u u − v v v by the following proposition.
where c ξ = min c i .

B. Curves
As pointed out earlier in [11], some important properties of a curve from a communication point of view are its stretch and small-ball radius. Given a curve s s s : [a, b] → R N , the Voronoi region V (x) of a point s s s(x) is the set of all points in R N which are closer to s s s(x) than to any other point of the curve. If H(x) denotes the hyperplane orthogonal to the curve at s s s(x), then the maximal small-ball radius of s s s is the largest r > 0 such that B r (s s s(x)) ∩ H(x) ⊂ V (x) for all x ∈ [a, b], where B r (s s s(x)) is the Euclidean ball of radius r centered at s s s(x). This means that the "tube" of radius r placed along the curve does not intersect itself. The stretch S(x) is the function ṡ s s(x) whereṡ s s(x) is the derivative of s s s(x). The length of a curve is given by b a S(x)dx. In this paper we will be interested in curves with large length and small-ball radius.

IV. THE TORUS LAYER SCHEME
The design of those curves in this section is essentially divided in two parts. First, we choose a collection of M tori on the surface of the Euclidean sphere S 2N −1 at least 2δ apart. The approach for doing this is via discrete spherical codes in R N . Second, we show a systematic way of constructing curves on each layer, via projection lattices in R N −1 . Finally, we give a description of the whole signal locus and summarize the encoding process.
For the Torus Layer Scheme, the unit interval will be partitioned into M intervals of different length, and each of them mapped into a curve on one of the layers. It is worth noticing that, for the special case M = 1, if we choose the torus associated to the vector c = 1 √ N (1, . . . , 1) to encode the information, then the scheme proposed here is exactly the one analysed in [11]. As we show next, for M > 1 the curves presented here outperform the ones presented in [11] (and also in [8]) in terms of length and small-ball radius.

A. Torus Layers
Given a target small ball radius δ, the first step of our approach is to define a collection T = {T 1 , T 2 , · · · , T M } of flat tori on S 2N −1 such that the minimum distance (6) between any two of them is greater than 2δ. This step is equivalent to design a N -dimensional spherical code SC + with minimum distance 2δ and such that its M codewords have non-negative coordinates.
Each point c c c ∈ SC + defines a hyperbox P c c c (5) and hence a flat torus T c c c in the unit sphere S 2N −1 . By (6) we can assert that the distance between two of those tori is at least 2δ.
There are several ways of constructing spherical codes that can be employed here, e.g. [3], [4] or even on layers of flat tori as introduced in [10]. We present next an example of a family of discrete spherical codes in R N that will be useful in Section VI.
, and cardinality M = N !. This set can be used in the first step of the construction described in this section. Note that and, for each t > 0, the codewords of SC c(t) are equidistant from tê ê e, the vector that determines the maximum volume torus Tê ê e . Moreover, for any fixed dimension N and d 0 ∈ R sufficiently small, there exists t > 0 such that d(t) = d 0 . This follows by observing that the equation has a positive root for Although the construction above is not the best one in terms of number of points for fixed d, it has the advantage of being highly symmetric and having a closed form for the spherical code minimum distance.

B. Curves on Each Torus
Let T c c c be a torus represented by the vector c c c ∈ SC + as defined in the previous section. On the surface of T c c c we consider curves of the form: where Provided that u u u ∈ Z N , gcd(u i ) = 1, those curves are closed (a (u 1 , . . . , u N )-type knot), and due to periodicity and local isometry properties of Φ c c c their lengths are 2π û u u . They are also the image through Φ c c c of the intersection between the set of lines 2πW , W = û u ux +n n n :n n n = n n nC and n n n ∈ Z N , and the box P c c c . For c =ê e e, these are exactly the curves analyzed in [11].
Let r c c c (u u u) be the minimum distance between two different lines in W . We have: where Pû u u ⊥ (n n n) denotes the orthogonal projection ofn n n onto the hyperplaneû u u ⊥ which is given by the standard projection formula Pû u u ⊥ (n n n) =n n n I N −û û u tû û û û û uû û u t .
If we consider Λ c c c = c 1 Z⊕. . .⊕c N Z, the rectangular lattice generated by matrix C, then r c c c (u u u) is the length of shortest non-zero vector of the projection 1 of Λ c c c ontoû u u ⊥ . Due to (7), the small-ball radius δ u u u,c c c of s s s Tc c c can be bounded in terms of r c c c (u u u) as follows: where c ξ = min i c i and c i > 0. Thus, for small values of δ u u u,c c c , we have δ u u u,c c c ≈ πr c c c (u u u). Our goal is to choose u u u in order to maximize r c c c (u u u). In addition, we also want to reach a contrary objective, which is the one of maximizing the arc length l u u u,c c c = 2π û u u of s s s Tc c c . The proportion (density) of the volume of the "tube" of radius πr c c c (u u u) inside P c c c is precisely the packing density of the lattice Pû⊥ (Λ c ), the projection of Λ c ontoû ⊥ , which is given by [6]: 1 In general, the projection of a lattice Λ onto a subspace H is not a lattice unless certain special conditions are met, e.g., when H ⊥ is spanned by primitive vectors of Λ [6]. This will be always the case in this paper, since H =û u u ⊥ for a primitive vectorû u u.
where ∆ N −1 is the density of the best lattice in dimension (N − 1) and V N −1 is the volume of the (N − 1)-dimensional unit sphere. For the case when all entries of c are equal, Λ c is equivalent to Z N and it was shown in [8] that we can make the above bound as tight as we want. We will show in Section V that this is also true for an arbitrary c i.e., that projections of the rectangular lattice Λ c c c can also yield dense lattice packings and therefore we can construct curves on the flat torus with the parameters arbitrary close to this bound.
on the flat torus T c c c and the line segment given by This curve in R 4 turns around u 1 -times the circle obtained by its projection on the first two coordinates, whereas turning around u 2 -times the circle of radius c 2 given by its last two coordinates (a type (u 1 , u 2 ) knot on the flat torus T c c c ). In this case, it is easy to calculate r c c c (u u u) since the density of the projection lattice is equal to one. In Figure 3 it is illustrated the curve (u 1 , u 2 ) = (4, 5), with c 1 > c 2 .

C. Encoding
and consider the bijective mapping Then the full encoding map s s s can be defined by The stretch of s s s is constant and equal its total length L and the small-ball radius of s s s is the minimum small-ball radius δ of the curves s s s T k , provided that the distance between any pair of torus in T is at least 2δ.
To encode a value x within [0, 1] we apply the map (17), with a scaling factor of √ P such that the average transmission power is P . The signal locus will be a set of M closed curves, each one lying on a torus layer T k and defined by a vector u u u k . This whole process is illustrated in Figure 3.

Fig. 3. Encoding Process
If the source is uniformly distributed over [0, 1], the encoding process presented above is a proper one, since all subintervals are equally stretched (see Section VI). For other applications, however, it could be worth considering another partition.

D. Decoding
Given a received vector y y y ∈ R 2N , the maximum likelihood decoding is findingx such that: 1] y y y − s s s(x) .
Since exactly solving this problem is computationally expensive we focus on a suboptimal decoder.
Let c c c i = (c i1 , c i2 , · · · , c iN ) be the closest point in ∈ SC + to γ γ γ and y y y i = c i1 cos be the projection of y y y in the torus T ci , i.e., From now on, we proceed the process by using a slight modification of the torus decoding algorithm [11] applied to the N -dimensional hyperbox P c c ci . The complexity of this algorithm is given by O(N u u u i 1 ), where u u u i is the vector that determines the curve s s s Ti . Hence, if M = O(max i u u u i 1 ), the overall complexity of the process described in this section is O(N max i u u u i 1 ), the same as for the torus decoding.

V. A SCALED LIFTING CONSTRUCTION
A. The construction The Lifting Construction was proposed in [8] as a solution to the problem of finding dense lattices which are equivalent to orthogonal projections of Z N along integer vectors ("fat-strut" problem). In this section we adapt that strategy in order to construct projections of the lattice Λ c c c which approximate any (N − 1) dimensional lattice (hence the densest one) with the objective of finding curves in R N approaching the bound (14). We adopt here the lattice terms as in [2]. For our purposes, the proximity measure for lattices will be the distance between their Gram matrices, as in [8]. This notion measures how close a lattice is to another one up to congruence transformations (rotations or reflections).
We consider the dual of a lattice Λ ∈ R N Λ * = {x x x ∈ span(Λ) : x x x, y y y ∈ Z ∀y y y ∈ Λ}, where span(Λ) is the subspace spanned by a basis of Λ. Now let Λ c c c = c 1 Z⊕. . .⊕c N Z be the rectangular lattice generated by the diagonal matrix C (and with Gram matrix CC t = C 2 ). By scaling Λ c c c , we may assume that c 1 = 1. With this condition, if P u u u ⊥ (Λ c c c ) * denotes the dual of the projection of Λ c c c through a vectorû u u = (1, u 2 c 2 . . . , u N c N ) (u i ∈ Z), then a generator matrix for Pû u u ⊥ (Λ c c c ) * is given by what can be derived as a consequence of Prop. 1.3.4 [6]. In what follows we derive a general construction of projections such that P u u u ⊥ is arbitrarily close to a target lattice Λ ∈ R N −1 .
Let Λ be a target lattice in R N −1 and consider a lower triangular generator matrix L * = (l * ij ) for Λ * . If Λ * w , w ∈ N is the sequence of lattices generated by the matrices (i) L * w = Pû u u ⊥ (Λ) * for someû u u ∈ R N and Proof: Applying elementary (integer) operations on L * w we can put it on form (18) for some integers u 2 , . . . , u n depending on w, hence L * w is a generator matrix for Pû u u ⊥ (Λ) * , proving the first statement. For the second statement, we clearly have (1/w)L * w → [L * 0 0 0] as w → ∞, where 0 0 0 is the (n−1)×n all-zero column vector. Therefore, Since the density of a lattice is a continuous function of the entries of its Gram matrix, it follows that the sequence of curves produced by the vectorsû û u approaches the bound (14) as w → ∞.
Example 3. Consider the hexagonal lattice [2], which is the best packing in two dimensions and is equivalent to its dual. One of its generator matrix is We apply the construction above and reduce, through elementary operations, the matrix L * w in order to put it on form (18). After re-scaling the rectangular lattice Λ c c c , we find the sequence of vectorŝ The projections of c 1 Z ⊕ c 2 Z ⊕ c 3 Z ontoû u u ⊥ w will be, up to equivalence, arbitrarily close to A 2 when w → ∞.

B. Comparisons: Curves in R 6
Here we compare our approach of constructing curves on torus layers with the curves constructed in [8] and [11] in terms of length for given small-ball radii. Given δ > 0, we first consider a set of flat tori associated to a spherical code in R 3 , with minimum distance greater than 2δ, as described in Section IV-A. Through the first inequality of (13), for each torus, we can find r c c c in order to guarantee that the curves on the flat tori will have small-ball radius at least δ (this is also done in the case of the curves on the torus c =ê ê e used in [11]). We then look for the larger element of the sequence of vectors that produces a projection with minimum distance at least r c c c . In Figure 4, the first curve from the bottom to the top represents the exponential sequence [11]. The second one is obtained by directly applying the Lifting Construction [8] to the hexagonal lattice and the last one displays the total length associated to our scheme.

VI. MEAN SQUARED ERROR ANALYSIS
The first step of the encoding process described in Section IV-C involves a choice of partition of the interval [0, 1]. If the source to be transmitted is uniformly distributed over [0, 1], it is intuitive that the best choice in terms of mse is the one such that the encoding map will have constant stretch. This fact is formalized in the next theorem.
Proof: First note that where (a) is due to the strict convexity of the function g(x) = x 3 for x > 0. Equality in (a) only holds when |I j |/L j = |I k |/L k , ∀k, j. This condition, together with n j=1 |I j | = 1, implies Equation (20).
It was proved in [11] that for fixed N and σ 2 , the mse of both the "spherical code" and the "shift-map" schemes decay, with respect to the channel power, with order O(1/P N ), provided that the parameter a [11, Sec. VI. A] is chosen suitably. This means that, although the surface of the sphere is a (2N − 1)-dimensional object, the mse exponent with respect to the channel power is roughly half of these dimensions for the spherical code. In what follows we present two results: 1) A constructive scheme based on Example V-B that increases of N ! the lengths of the scheme proposed in [11], even with the improvements of the Lifting Construction [8]. This will yield an asymptotic behavior comparable to O(1/P N ), but with a better performance when N increases. 2) A non-constructive asymptotic argument showing that it is possible to "recover" the (N − 1)-dimensions lost by mapping the N -dimensional shift-map to a sphere in R 2N and achieve decay order of O(1/P − (2N −1) ). For the first result, let N be fixed and let c c c(t) be given by Equation (8). Recall thatê ê e = 1/ √  N (1, . . . , 1). For ρ > 0 sufficiently small, there is t such that the tori in the set SC c(t) have minimum distance 2ρ. Moreover, there isû u u ∈ Λ c c c(t) arbitrarily close to the bound (14). The same vector u u u can be used for any c c c ∈ SC c c c(t) just by interchanging its coordinates, yielding the same parameters for all tori. Since we have N ! tori in the set SC c c c(t) , the total length L T L produced is given by: (21) For the Lifting Construction and same small-ball radius, we have As ρ → 0, we can make both ε 1 and ε 2 vanish, and then Now, by making t sufficiently small (but keeping the smallball radius greater than ρ), we have In other words, where the approximation is good when we allow the small-ball radius to be small (this is the case when the SNR is high). The next theorem states the asymptotic improvements in terms of "recovering" the N − 1 dimensions lost by the spherical code scheme in [11]. Its proof, however, is nonconstructive. The intuitive idea is that the spherical uses only one torus (an N -dimensional object) on the surface of a sphere, while the whole sphere can be filled through the foliation by flat tori. VII. SIMULATIONS We now present some simulation results in order to illustrate the performance of our proposed scheme. We consider sources uniformly distributed over the interval [0, 1] and normally distributed with variance σ 2 s = 1/2. As a benchmark we chose the spherical code scheme (V&C) presented in [11], since this scheme has comparable performance with [12], as shown in their simulations. We also plotted the curves corresponding to a simple linear modulation. The simulation results correspond to 50000 samples with 1 to 6 expansion rate (N = 3) and the performance is measured in terms of 1/mse as a function of the SNR = P/σ 2 .

A. Uniform sources
In Figure 5 (top), the Torus Layer Scheme (TL) performance for M = 6 tori, designed as in Example 1 with t = 0.6, and projection vector u = (1, 2, 198) is displayed. The spherical code scheme V&C was simulated for a = 18. The parameters were chosen such that both schemes reach the asymptote for the same SNR (i.e., have approximately the same small-ball radius). As expected, our scheme outperforms (V&C) in the low noise regime (about 13dB higher in this example).    1, 4, 34). The spherical code scheme V&C was simulated also for a = 18. These parameters were chosen such that both schemes achieve about the same performance in low noise regime (same asymptote). In this case, our scheme reaches the asymptote for a smaller SNR (5dB in this example). In both graphics it is possible to see that linear modulation is a good choice only for very small SNR.

B. Gaussian sources
Although the theory is suitably developed for uniform sources, we present in this section a possible approach for the Gaussian case and also some simulation results. Let x be drawn according to a normal distribution N (0, σ s ) and let p(x) be the pdf of x. In order to use our coding scheme we need to map the real line into sub intervals of [0, 1] and then in layers of flat tori.
Like in the uniform case, we consider a collection T = {T 1 , . . . , T M } of M tori designed as described in Section IV-A. For each one of these tori, we have a curve s s s T k (x) with length L k and the total length is L = M k=1 L k . Our first step to deal with Gaussian sources is to split the real line into M sub intervals {Q 1 , Q 2 , · · · , Q M } such that the area under p(x) with domain restricted to Q k is equal to L k L . Let {x 1 , x 2 , · · · , x M −1 } be the endpoints, such that the intervals are defined as follows: g(x) x x y y g −1 (ŷ) Then we apply the optimal companding function [7] g : R → [0, 1] to map the real line into the interval [0, 1]. The images {g(x 1 ), g(x 2 ), · · · , g(x M −1 )} induce a split of the interval [0, 1] into M pieces {I 1 , I 2 , · · · , I M }, such that with lengths {L I1 , L I2 , · · · , L I M } and then we can define our bijective mapping for the Gaussian case as The full encoding map s s s as well as the decoding process will be similar to the uniform case. Once we have the estimateŷ we must invert the companding function to getx = g −1 (ŷ) and then compute the mse. This process is illustrated in Figure  6 (left). In Figure 6 (top) we show simulation results for a Gaussian source with σ s = 0.5. The parameters were the same as for the Uniform source simulation in Figure 5 (top). As we can see, the threshold is reached for a higher SNR than in the uniform case, but the TL scheme maintain some advantage over V&C.
We finish this section with a remark on the implementation. Since the curves constructed from our method are closed, if the sent value is one extreme value of the interval I j = [L j−1 /L, L j /L] it may happen that the decoder wrongly interpret it as the other extreme. In other words, if L j−1 /L+ε is sent, then with a non-negligible probability, the decoder will output L j /L. To prevent these errors, the encoder needs to "shrink" the interval I j by a factor α ∈ (0, 1), such that the curve is "opened", separating the encoded extremes values apart. However, this process deteriorates the low noise performance, so that α needs to be calibrated. In our examples, it sufficed to take any α between 0.7 and 0.8. This issue was briefly commented in [11].

VIII. CONCLUSION
The problem of transmitting a continuous alphabet source over an AWGN channel was considered through an approach based on curves designed in layers of flat tori on the surface of a (2N )-dimensional Euclidean sphere. This approach explores connections with constructions of spherical codes and is related to the problem of finding dense projections of the lattice This work is a generalization of both the scheme proposed in [11] and the Lifting Construction in [8]. As a consequence, our scheme compares favorably to previous works in terms of the tradeoff between total length and small-ball radius, which is a proper figure of merit for this communication system.
In spite of the improvements in terms of length versus smallball radius, the constructiveness, homogeneity and overall complexity of the decoding algorithm are features preserved from [11]. Simulations also show a good scaling of the mse with the channel SNR. Further questions include applications to sources that do not have limited support, or when it is hard to employ a companding function (e.g., Gaussian mixtures), and generalization to other bandwidth expansion ratios than 1 : 2N (the general case is to consider K to N expansion mappings, when 1 < K < N ). In the more general K : N bandwidth expansion context we must consider Kdimensional manifolds in R N , and the analog codes could be built for instance considering projections of lattices onto (N − K)-dimensional subspaces and a generalized version of the shift-map system described in [11].

ACKNOWLEDGMENT
The authors would like to thank the Centre Interfacultaire Bernoulli (CIB) -EPFL, where part of this work was developed, during the special semester on Combinatorial, Algebraic and Algorithmic Aspects of Coding Theory, and Vinay Vaishampayan for helpful discussions on analog sourcechannel coding. The authors also thank the reviewers for the suggestions that improved the manuscript, specially for an observation that led us to Theorem 3.

APPENDIX A
The big-O and big-Θ notations are employed throughout this appendix. We say that f (n) = O(g(n)) if there exists n 0 and a constant c such that |f (n)| ≤ c|g(n)| for n > n 0 .
We say that f (n) = Θ(g(n)) if f (n) = O(g(n)) and g(n) = O(f (n)). We have the following technical lemmas: Lemma 1. Consider a family of analog codes given by the map (17) normalized to average power P . Suppose that the total length and small-ball radius of the family satisfies L = Θ(ρ −(k−1) ) for some k > 1, as ρ → 0. Then, for any P > 0 and any arbitrarily small µ > 0, there is a choice of parameters such that the mse decays with order O(P −k+µ ).
Proof: The proof is an application of the technique in [9, Appendix A] or even [11, Sec. VI. B], that we briefly describe for sake of completeness. If P ("jump") denotes the probability that the estimatex is decoded to the wrong fold of the curve, we can bound it by Q( √ P ρ/σ), where Q(x) is the tail probability of a standard normal distribution. On the other hand, when there is no jump, the mse is proportional to σ 2 /(α 2 L 2 ), where L is the length of the curve and α = √ P . Since ρ → 0, there is a choice of parameters such that ρ = Θ(P −1/2+μ ), forμ > 0 arbitrarily small. If we choosē µ = µ/(2k − 2), then √ P ρ = Θ(Pμ) and from the previous observations: Proof: From the Chabauty-Shannon-Wyner bound [3, Thm. 1.6.2], there exists a spherical code with minimum distance 2ρ and number of codewords at least M = Θ(ρ − (N −1) ). In fact, by considering only the volume of the positive part of the sphere (x i ≥ 0 for all i), the same argument shows that there exists a spherical SC + with codewords having positive coordinates and satisfying |SC + | = Θ(ρ − (N −1) ). Now, denote by SC ε + the subcode of SC + such that c ij > ε for some positive small ε. We have M i=1 N j=1 c ij ≥ c c ci∈SC ε + N j=1 c ij ≥ ε N |SC ε + |. As ε → 0, |SC ε + | → |SC + | = Θ(ρ −(N −1) ) , however if ε goes to 0 too fast with respect to the distance, we may be deleting too many codewords to construct SC ε + and hence will not achieve the desired exponent. The choice ε = ρ µ/N for arbitrarily small (but positive) µ does the trick.
Proof of Theorem 3: If the spherical code SC + = {c c c 1 , . . . , c c c M } has M words and minimum distance 2ρ sufficiently small, from the Scaled Lifting Construction (Section V) it is possible to find vectors u u u i such that their norms are close to the bound (14), hence for some ε, the total length will be where c ij is the j-th coordinate of torus T i and ε → 0 as ρ → 0. Thus desconsidering the "sum of the product" term, the length would grow with order ρ −(N −1) . From Lemma 2, we can choose c c c i such that the the sum has order Θ(ρ −(N −1) ), hence L = Θ(ρ −(2N −2) ), and from Lemma 1 the result holds.


text:
A Constraint Propagation Approach to Probabilistic Reasoning

The paper demonstrates that strict adherence to probability theory does not preclude the use of concurrent, self-activated constraint-propagation mechanisms for managing uncertainty. Maintaining local records of sources-of-belief allows both predictive and diagnostic inferences to be activated simultaneously and propagate harmoniously towards a stable equilibrium.

INTRODUCTION: BAYES NEIWORKS AND CONSTRAINTS PROPAGATION
Scholarly textbooks on probability theory often create the impression that to construct an adequate representation of probabilistic knowledge we must first define a joint distribution function on all propositions and their combinations, i.e., on the so-called universe of discern ment. The computational difficulties involved in articulating, validating, storing and manipu lating such distributions seem insurmountable and have discouraged many AI researchers from openly using probabilistic formalisms in expert systems. In truth, however, these difficulties are merely mathematical fiction, and do not plague common-sensical approaches to probabilistic reasoning. In a sparsely connected world like ours, it is fairly clear that probabilistic knowledge, in both man and machine, should not be represented by entries of a giant joint distribution table, but rather by a network of low-order probabilistic relationships between small clusters of semantically related propositions. One effective representation of such rela tionships is provided by Bayesian Networb: a class of networks typified by the use of "influence diagrams" in decision analysis [Howard and Matheson, 1984] and "inference networks" in expert systems [Duda, Hart, and Nilsson, 1976]. (The alternative network representation using Mar kov fields [Pearl, 1985] will not be discussed here.) Bayes Networks are directed acyclic graphs in which the nodes represent propositions (or variables), the arcs signify the existence of direct causal influences between the linked pro positi�ns, and the strengths of these influences are quantified by conditional probabilities (Fig   ure 1 ). Thus, if the graph contains the variables .r1, •.. ,Xn, and S, is the set of parents for vari able .r1, then a complete and consistent quantification can be attained by specifying, for each node x1, an assessment of P(x1 I S1). The product of all these assessments, constitutes a joint-probability model which supports the assessed quantities. That is, if we compute the conditional probabilities P(x, IS,) dictated by P(.r1, . . . ,.rn)• the original assess ments are recovered. For example, the distribution corresponding to the graph of Figure 1  An important feature of Bayes network i:'l that it provides a clear visual representation for many independence relationships embedded in the underlying probabilistic model. The cri terion for detecting these independencies is based on graph eeparation: namely, if all paths between x1 and x1 are "blocked" by a a subset S of variables, then Xt ie independent of XJ given the values of the variables in S. Thus, each variable Xt is independent of both its siblings and its grandparents, gh�en the values of the variables in its parent set s,. For this "blocking• cri terion to hold in general, we must provide a special interpretation of separation for nodes that share common children. \Ve say that the pathway along arrows meeting head-to-head at node xk. is normally "blocked", unless Xt: or any of its descendants is in S. In Figure 1, for example, x2 and X3 are independent given S1 = {xl} Or S2 = {X1p%4}, because the two paths between X2 and X] are blocked by either one of these sets. However, x2 and X3 may not be independent given S3 = {x1p%J, because .%6, as a descendant of xs , "unhlocks• the head-to-head connection at xs, thus opening a pathway between x2 and x3.
Once a Bayes network is established, it can he used to represent the deep causal knowledge of a domain expert and can provide probabilistic answers to all queries regarding the interpretation of evidential information in that domain. Ideally, however, we would also like to treat such a network as a computational architecture that facilitates the interpretation of data at th� knowl� d ge level its�lf: we want to view the links not merely as codes for storing factual knowledge but also as pathways and activation centers which both direct and propel the flow of data in the process of querying and updating that knowledge.
The process of self-activated interpretation is conveniently described in terms of constraint-propagation or relaxation paradigm. Each link in the network represents constraints on the possible values that the belief parameters can take at the two nodes connected by the link. Updating is accomplished by successiYely finding unsatisfied constraints and satisfying them by modifying the belief parameters, thus bringing ·out of kilter" constraints hack to re laxed status. Relaxing one constraint usually perturbs its neighbors, so relaxation results in a multi-directional propagation process which reaches a static equilibrium when all constraints are satisfied.
The relaxation paradigm has several advantages over other mechanisms of uncertainty management. It permits knowledge to be specified declaratively without regard for the specific control method used. It is readily implementable by pattern-oriented rule-based languages as well as by object-oriented languages. In the former, the antecedents of the rules alert to viola tions of constraints and their consequent parts specify corrective actions. In the latter, each node is an object of the same generic type and the constraints are the messages by which neighboring objects communicate. Moreover, relaxation can be executed in parallel by a large array of simple autonomous processes, thus providing a reasonable model of human cognitive behavior.
While constraint-propagation mechanisms have found several applications in AI, such as vtston [Rosenfeld, Hummel and Zucker,  1 980], their use in evidential reasoning has been limited to non-Bayesian formalisms [e.g. Lowrance, 1982]. The reason has been several-fold.
First, the conditional probabilities characterir:ing the links in the network do not seem to impose definitive constraints on the probabilities that can be assigned to the nodes. The quantifier P(A IB) only restricts the belief accorded to A in a very special set of circumstances: namely, when B is known to be true with absolute certainty, and when no other evidential data is available. Under normal circumstances, all internal nodes in the network will be subject to some uncertainty and, more seriously, after observing evidence � the conditional belief in A is no longer governed by P(AIB) but by P(AIB, �), which may be totally different. The result is that any assignment of beliefs, P(A) and P(B), to propositions A and B can be consistent with the value of P(AIB) initially assigned to the link connecting them; therefore, no violation of constraint can be detected locally.
Next, the difference between P(AIB, 6) and P(A!B) seems to suggest that the weights on the links should not remain fixed but should undergo constant adjustment as new evidence ar rives. This, in turn, would require an enormous computational work and would wipe out the advantages normally associated with propagation through fixed constraints.
Finally, the fact that evidential reasoning involves both top-down (predictive) and bottom-up (diagnostic) inferences has caused apprehensions that, once we allow the propaga tion process to run its course unsupervised, pathological cases of instability, deadlock, and cir cular reasoning will develop. Indeed, if a stronger belief in a given hypothesis means a greater expectation for the occurrence of its various manifestations and if, in tum, a greater certainty in the occurrence of these manifestations adds further credence to the hypothesis, how can one avoid infinite updating loops when the processors responsible for these propositions begin to communicate with one another! Likewise, Lowrance [1 982] expresses concern that if proposi tion B influences the belief in A via P(A!B) and proposition A influences the belief in B via P(BjA), then the "feedback between A and B would eventually drive the two beliefs to the mar ginals," thus preventing any further updating from occurring. This paper shows that coherent and stable probabilistic reasoning can be accomplished by local propagation mechanisms while keeping the weights on the links constant throughout the process. This is made possible by characterizing the belief in each proposition by a vector of parameters, one for each port. Each component in the vector stands for the degree of sup port that the host proposition obtains from one of its neighbors. We show that, in certain net works, maintaining such a breakdown record of the sources of belief facilitates efficient updat- The relaxation paradigm has several advantages over other mechanisms of uncertainty management. It permits knowledge to be specified dedaratively without regard for the specific control method used. It ill readily implementable by pattern-oriented rule-balled languages as well as by object-oriented languages. In the former, the antecedent!! of the rules alert to viola tions o( c onstraints and their consequent parts specify corrective actions. In the latter, each noc.le is an object of the same generic type and the constraints are the messages by which neighboring objects communicate. Moreover, relaxation can be executed in parallel by a large array of simple autonomous proce!lses, thus providing a reasonable model of human cognitive behavior.
While constraint-propagation mechanisms have found several applications in AI, such as vision {Rosenfeld, Hummel and Zucker, 1976; Waltz, H/72] and truth maintenance [McAllester, 1980], their use in evidential reasoning has been limited to non-Bayesian formalisms (e.g. Lowrance, 1982]. The reason has been several-fold. First, the conditional probabilities characterizing the links in the network do not seem to impose definitive constraints on the probabilities that can be assigned to the nodes. The quantifier P(A jB) only restricts the belief accorded to A in a very special set of circumstances: namely, when B is known to be true with absolute certainty, and when no ether evidential data is available. Under normal circumstances, all internal nodes in the network will be subject to some uncertainty and, more seriously, after observing evidence t the conditional belief in A is no longer go>erned by P(AjB) but by P(AIEJ, t), which may be totally different. The result is that any assignment of beliefs, P(A) and P(B), to propositions A and B can be consistent with the value of P(AIB) initially assigned to the link connecting them; therefore, no violation of constraint can be detected locally.
Next, the difference between P(A \B, t) and P(A\B) 11eems to suggest that the weights on the links should not remain fixed but should undergo constant adjustment as new evidence ar rives. This, in turn, would require an enormous computational work and would wipe out the advantages normally associated with propagation through fixed constraints.
Finally, the fact that evidential reasoning involves both top-down (predictive) and bottom-up (diagnostic) inferences has caused apprehensions that, once we allow the propaga tion process to run its course unsupervised, pathological cases of instability, deadlock, and cir cular reasoning will develop. Indeed, if a stronger belief in a given hypothesis means a greater expectation for the occurrence of its various manifestations and if, in turn, a greater certainty in the occurrence of these manifestations adds further credence to the hypothesis, how can one avoid infi nite updating loops when the processors responsible for these propositions begin to communicate with one another! Likewise, Lowrance (1982] expresses concern that if proposi tion B influences the belief in A via P(A IB) and proposition A influences the belief in B via P(BjA), then the "feedback between A and B would eventually drive the two beliefs to the mar ginals," thus preventing any further updating from occurring. This paper shows that coherent and stable probabilistic reasoning can he accomplished by local propagation mechanisms while keeping the weights on the links constant throughout the process. This is made possible by characterizing the belief in each proposition by a vector of parameters, one for each port. Each component in the vector stands for the degree of sup port that the host proposition obtains from one of its neighbors. We show that, in certain net works, maintaining such a breakdown record of the sources of belief facilitates efficient updat- ing of parameters by constraint-propagation, and that the network relaxes to a stable equilibri um consistent with the axioms of probability theory, in time proportional to the network diam eter. This record of parameters is also postulated as the mechanism which permits people to trace hack the sources of beliefs for the purpose of constructing explanatory arguments.

2.
PROPAGATION IN SINGLY -CONNECJ'ED NEIWORKS \Vc shall first consider Bayes networks which are singly connected, that is, there is at most one underlying path between any pair of nodes. Propagation algorithms for such networks were developed by Pearl [1982], for the special case of trees, and were later generalized by Kim and Pearl [1983] to admit nodes with multiple parents. To establish the notation necessary for treating more general networks, we shall reiterate here the results of Kim and Pearl and cast them in the context of constraint propagation.
Let each node in the network represent a multivalued variable which might stand for a collection of mutually exclusive hypotheses (e.g., identity of organism: ORG1, ORG2, ... ) or a col lection of possible ohserntions (e.g. patient's temperature: high, medium, low). Let a variable be labeled by a capital letter, e.g., A, B, C, ... , and its possible values subscripted, e.g., A1o A2, ... , A,. Each group of arrows pointing at a given node is quantified by a fixed condition al probability matrix. For example, the arrows B .. A and C .. A in Figure 2, will be quantified by a matrix M, with entries: Mu�c = P(AIIBJ,Ck)· These matrices quantify the strength of influence between causes and their conse quences. Additionally, they contain the information for deciding how the belief in one cause is affected by evidence bearing on another, once their common manifestation is observed. This in teraction, colloquially termed "explaining away," is a prevailing pattern of human reasoning, and occurs even when the causal variables are marginally independent. For example, when a physician discovers evidence in favor of one disease, it reduces the credibility of other diseases, although the patient could be suffering from two or more disorders simultaneously.
Instantiated variables, constituting the incoming evidence or data will be denoted by D.
For the sake of clarity we will distinguish between the fixed conditional probabilities that label the links, e.g. P(A 18), and the dynamic values of the updated node probabilities. The latter will be denoted by BEL(A1), which reflects the overall belief accorded to proposition A1 by all data so far received. Thus, where D is the value combination of all instantiated variables.

Fusion Equations
Consider a fragment of a singly connected network, as depicted in Figure 2. The link B .. A partitions the graph into two parts: an upper. subgraph G,t1., and a lower subgraph G&, the complement of G�. These two graphs contain two sets of data which we shall call D� and DB,.. , respectively. Likewise, the links C .. A, A .. X, and A .. Y define the subgraphs G�, G_.\K, and GA"r which contain the data sets D�, Dix, and DA"r, respectively. Since A is a common child of B and C, it does not separate G,t1. and Gt;. apart. However, it does separate the following three subgraphs: G1.t U GC,., GA"f, and G.,U., and we can write and (3) the fixed conditional probability matrix, P(AjB, C), which relates the variable A to its immediate causes. Accordingly, we let each link carry two dynamic parametent, 'If and �. and let each node store the information contained in P( AjB , C).
With these parameten at hand, the fusion equation (5) Assume that the vectors 'If and � are stored with each link, "' at the tail of the arrow and � at its head. Our task is now to prescribe how the values of 'If and � at a given link are constrained by the corresponding parameters at neighboring links.
Upda.ting k Starting from the definition of �A ( B, ) ,.. P(D &\B , }, we partition the data DiA into its components: A, DAi, DA;r, D't_, and summing over all values of A and C we get (10) Eq.(lO) shows that only three parameters (in addition to the conditional probabilities P( AjB , C ) ) need to he involved in updating the diagnostic parameter vector �A (B) : 'lfA ( C), �x(A ) , and �r(A ) . This is expected since DiA is completely summarized by X, Y, and C.
The boundary conditions are established as follows: Data-no d es: If the J .,;, state of B is known to be true, we add to B a dummy son Z, and set �z(B) = (0, ... ,0,1,0, ... ,0) with 1 at the l' position.

Root-no d es:
If B is a node with no parents, we add to B a dummy father Z instantiated to Z=TRUE, and set the link matrix P(Bjz=1RUE) equal to the prior P(B).

Constraints Propagation
So far we have viewed the links of the network as message-carrying devices through which the node processors communicate. They can also be viewed as constraint-maintaining agents. Imagine that each node is characterized by several parameter vectors, one for each of its ports. The 1r's are placed on the outgoing ports :1nd the �·s on the incoming ports. In node A of Figure 2, for example, the parameters 1rx(A) and 1ry{A) will be placed on the lower two ports (facing the children X and Y) while �A(B) and �A(C) will be placed on the upper ports (facing the parents). Imagine also that a node is permitted to compare its own set of parame ters with those of its neighbors. Equations (10) and (11) then dictate how the link matrices P(A 1B ,C) impose equality constraints between the parameters of one node and those of its neighbors. If these equalities are satisfied (within some reasonable tolerance), no actiYity takes place. However, if any of these equalities is violated, the responsible node is activated to revise its violating parameter and set it straight. This, of course, will activate similar revisions at neighboring nodes and will set up a multidirectional propagation process.
Eqs. (10) and (11 ) demonstrate that a perturbation of the causal parameter, '1'1, will not affect the diagnostic parameter, �. on the same link, and vice vena. The two are orthogonal to each other since they depend on two disjoint sets of data. Therefore, no feedback or "circular reasoning" can take place --any perturbation of beliefs due to new evidence propagates through the network and is absorbed at the boundary without reflection, resulting in a new equilibrium state compatible with the newly observed eviden . ce.
In summary, we see that the architectural objectives of propagating beliefs coherently, through an active network of primitive, identical, and autonomous processors can be fully real ized in singly-connected graphs. Instabilities due to cyclic inferences are· avoided by. using mul tiple, source-identified belief parameters, and equilibrium is guaranteed to be reached in time . proportional to the network diameter.
The primitive processors are simple, repetitive, and require no working memory except that used in matrix multiplications. Thus, this architecture lends itself naturally to hardware implementation, capable of real-time interpretation of rapidly changing data. It also provides a reasonable model of neural nets involved in cognitive tasks such as visual recognition, reading comprehension (Rumelhart, 1976], and associative retrieval (Anderson, 1983), where unsuper vised concurrent processing is an uncontested mechanism.

PROPAGATION IN MULTIPLY-CONNECTED NEIWORKS
The efficacy of singly-connected networks in supporting autonomous propagation raises the question of whether similar propagation mechanisms exist in less restrictive networks (like the one in Figure 1), where multiple parents of common children also possess common ances tors, thus forming loops in the underlying network. If we ignore the existence of loops and per mit the nodes to continue communicating with each other as if the network was singly connected, it will set up messages circulating indefinitely around the loops and the process most probably will not converge to a coherent equilibrium.
A straightforward way of handling the network of Figure 1 would be to appoint a local interpreter for the loop .l'lf x2, x3, %.5 that will pass messages directly between x1 and x.s, account ing for the interactions between x2 and %3. This amounts basically to collapsing nodes x2 and x3.
into a single node, representing the compound variable (xlt xv. This method works well on small loops, but as soon as the number of variables exceeds 3 or 4, collapsing requires handling huge matrices and washes away the natural conceptual structure embedded in the original net work. A second method of propagation is based on "stochastic relaxation" (Gem an and Ge m an, 1984). Each processor interrogates the states of the variables within its influencing neigh borhood, computes a belief distribution for the values of its host variable, then randomly selects one of these values with probability given by the computed distribution. The value chosen will subsequently be interrogated by the neighbors upon computing their beliefs, and so on. This scheme is guaranteed convergence, but usually requires very long relaxation times to reach a steady state. The method that we found most promising iB 'baBed on the ability to change the connec tivity of a network, and render it singly connectecl by instantiating a selected group of vari ables. In Figure 1, for example, instantiating z1·to some value would block the pathway z2, zlt z3 and would render the rest of the network singly connected, where the propagation techniques of the preceding section are applicable. Thus, if we wish to propagate the impact of an observed data, say at xt,, to the entire network, we first assume .x1 = 0, propagate the impact of Zts to the variables z2, ... ,z5, repeat the propagaltion under the assumption z1 = 1 and, final ly, linearly combine the two results weighed by the prior probability P ( .xl)· The legitimacy of this method is clearly seen from the ever-so-faithful conditioning rule of probability: P(x2, · · · xtJ = l: P(z2, . .. ,.fn I z 1) P(zl) .r1 The novelty here is that while in the ordinary use of the rule we seek a conditioning nriable that renders some other variables independent (separating the network into unconnect. ed frag ments), we now settle for more modest goals, requiring only that the resulting conditional pro bability P (.x2, •••• Ztslx1) have a singly-connected network representation. Note that the choice of .x2 as a conditioning variable would be equally adequate, but z5 is a bad choice, since instan tiating this variable would not disconnect the pathway .x2, .x5, .1'3.
The tool of conditioning is not foreign to human reasoning. The terms "hypothetical" or "assumption-ba!led" reasoning, "reasoning by cases," and "envisioning" all refer to the same basic mechanism of selecting a key variable, binding it to some of its values, deriving the conse quences of each binding separately, and integrating those consequences together. Reasoning by cases is very frequently used in explanation and argumentation -showing that diametrically opposed assumptions impart equal credence to a given proposition constitutes a convincing ar gument for assigning that credence to the proposition. Likewise, showing that different sets of circumstances would require the same type of action constitutes a strong argument for recom mending that action.
Although conditioning was introduced here as a sequential process, it can easily be im plemented in parallel, to comply with our propagation paradigm. Instead of a single set of 1T -� parameters, each node should maintain Beveral Buch sets, one for each value of the condition ing variable. The constraint equations (Eqs. (10) and (11)) are checked for each of these sets individually, and the appropriate parameters updated. Additionally, the prior probability of the conditioning variable can also pass along from node to node so that when the overall belief in a given proposition is required, the proper weightB will be available to perl'orm the averag mg.
By contrast, under conditioning routines, node x2 (as well as x3) will prepare for x.s, not a single parameter 1T .r 5 (xv, but two: together with the prior probability P(x1) (see Figure 3). Receiving these two forces x.s to follow suit and compute two sets of parameters as well: 1T�, (x.s) = � P(x.s�2.x3)1T;,(xv1T;.(x3) 1'2.1'3-0,1 Now imagine that some evidence is obtained, say X6 = 1. Node X6 will provide x5 with the diagnostic parameters: )..r,(x .s) = P(X6 = 1� s) x.s = 0,1 and subsequently, X5 will deliver to X2 two sets of ).1'5(XV parameters: A similar set will be computed for X3. To calculate the overall belief in a proposition, say X2, we make use of the prior probability P(x1) and compute the average BEL (xv = po 1T;, (xv >.;s (xv P(x 1 = O) + P 1 1Ti, (xv >.is (xv P(x 1 -1) It is essential to note that the conditioned parameters must propagate as separate quan tities and only be averaged when the final belief measures are to be calculated. The reason is that the conditioning variable influences the other variables in the loop along two separate paths, clockwise and counterclockwise. If we were to pass along the averaged quantities, in stead of the individual constituents, it would amount to counting the prior information twice, instead or once.

CONCLUSIONS
The architectural objectives of propagating beliefs coherently by self-activated and con current mechanisms are fully realizable in singly-connected graphs. In multiply-connected


text:
Fingerprinting with Equiangular Tight Frames

Digital fingerprinting is a framework for marking media files, such as images, music, or movies, with user-specific signatures to deter illegal distribution. Multiple users can collude to produce a forgery that can potentially overcome a fingerprinting system. This paper proposes an equiangular tight frame fingerprint design which is robust to such collusion attacks. We motivate this design by considering digital fingerprinting in terms of compressed sensing. The attack is modeled as linear averaging of multiple marked copies before adding a Gaussian noise vector. The content owner can then determine guilt by exploiting correlation between each user's fingerprint and the forged copy. The worst-case error probability of this detection scheme is analyzed and bounded. Simulation results demonstrate the average-case performance is similar to the performance of orthogonal and simplex fingerprint designs, while accommodating several times as many users.

I. INTRODUCTION
D IGITAL media protection has become an important issue in recent years, as illegal distribution of licensed material has become increasingly prevalent. A number of methods have been proposed to restrict illegal distribution of media and ensure only licensed users are able to access it. One method involves cryptographic techniques, which encrypt the media before distribution. By doing this, only the users with appropriate licensed hardware or software have access; satellite TV and DVDs are two such examples. Unfortunately, cryptographic approaches are limited in that once the content is decrypted (legally or illegally), it can potentially be copied and distributed freely.
An alternate approach involves marking each copy of the media with a unique signature. The signature could be a change in the bit sequence of the digital file or some noise-like distortion of the media. The unique signatures are called fingerprints, by analogy to the uniqueness of human fingerprints. With this approach, a licensed user could illegally distribute the file, only to be implicated by his fingerprint. The potential for prosecution acts as a deterrent to unauthorized distribution.
Fingerprinting can be an effective technique for inhibiting individual licensed users from distributing their copies of the media. However, fingerprinting systems are vulnerable when multiple users form a collusion by combining their copies to create a forged copy. This attack can reduce and distort the colluders' individual fingerprints, making identification of any particular user difficult. Some examples of potential attacks involve comparing the bit sequences of different copies, averaging copies in the signal space, as well as introducing distortion (such as noise, rotation, or cropping).
There are two principal approaches to designing fingerprints with robustness to collusions. The first approach uses the marking assumption [1]: that the forged copy only differs from the colluders' copies where the colluders' copies are different (typically in the bit sequence). In many cases, this is a reasonable assumption because modifying other bits would likely render the file unusable (such as with software).
Boneh and Shaw proposed the first known fingerprint design that uses the marking assumption to identify a member of the collusion with high probability [1]. Boneh and Shaw's method incorporates the results of Chor et al., who investigated how to detect users who illegally share keys for encrypted material [2]. Schaathun later showed that the Boneh-Shaw scheme is more efficient than initially thought and proposed further improvements [3]. Tardos also proposed a method with significantly shorter codelengths than those of the Boneh-Shaw procedure [4]. Several recent works investigate the relationship between the fingerprinting problem and multiple access channels, and they calculate the capacity of a "fingerprint channel" [5]- [8]. Barg and Kabatiansky also developed "parent-identifying" codes under a relaxation of the marking assumption [9], and there have been a number of other works developing special classes of binary fingerprinting codes, including [10]- [15].
The second major approach uses the distortion assumption. In this regime, fingerprints are noise-like distortions to the media in signal space. In order to preserve the overall quality of the media, limits are placed on the magnitude of this distortion. The content owner limits the power of the fingerprint he adds, and the collusion limits the power of the noise they add in their attack. When applying the distortion assumption, the literature typically assumes that the collusion linearly averages their individual copies to forge the host signal. Also, while results in this domain tend to accommodate fewer users than those with the marking assumption, the distortion assumption enables a more natural embedding of the fingerprints, i.e., in the signal space.
Cox et al. introduced one of the first robust fingerprint designs under the distortion assumption [16]; the robustness was later analytically proven in [17]. Ergun et al. then showed that for any fingerprinting system, there is a tradeoff between the probabilities of successful detection and false positives imposed by a linear-average-plus-noise attack from sufficiently large collusions [18]. Specific fingerprint designs were later studied, including orthogonal fingerprints [19] and simplex fingerprints [20]. There are also some proposed methods motivated by CDMA techniques [21], [22]. Jourdas and Moulin demonstrated that a high rate can be achieved by embedding randomly concatenated, independent short codes [23]. Kiyavash and Moulin derived a lower bound on the worstcase error probabilities for designs with equal-energy fingerprints [24]. An error probability analysis of general fingerprint designs with unequal priors on user collusion is given in [25]. Some works have also investigated fingerprint performance under attack strategies other than linear averaging [26], [27] and under alternative noise models [28].
When working with distortion-type fingerprints, some embedding process is typically needed. This process is intended to make it difficult for the colluders to identify or distort fingerprints without significantly damaging the corresponding media in the process. For instance, if the identity basis is used as an orthogonal fingerprint design, then three or more colluders can easily identify and remove their fingerprints through comparisons. Indeed, different signal dimensions have different perceptual significance to the human user, and one should vary signal power strengths accordingly. There is a large body of work in this area known as watermarking, and this literature is relevant since fingerprinting assigns a distinct watermark to each user. As an example, one method of fingerprint embedding is known as spread spectrum watermarking. Inspired by spread spectrum communications [29], this technique rotates the fingerprint basis to be distributed across the perceptually significant dimensions of the signal [16]. This makes fingerprint removal difficult while at the same time maintaining acceptable fidelity. For an overview of watermarking media, see [30], [31].
The present paper proposes a fingerprint design under the distortion assumption. Specifically, we propose equiangular tight frames for fingerprint design and analyze their performance for the worst-case collusion. Moreover, through simulations, we show that these fingerprints perform comparably to orthogonal and simplex fingerprints on average, while accommodating several times as many users. Li and Trappe [22] also used fingerprints satisfying the Welch bound, but did not use tight frames, designed the decoder to return the whole collusion, and did not perform worst case analysis. Use of compressed sensing for fingerprint design was first suggested in [32] and [33], follow by [34]. However, [34] and [33] focused on detection schemes with Gaussian fingerprints. Additionally, [35] examined combinatorial similarities of fingerprint codes and compressed sensing measurement matrices.
We present the description of the fingerprinting problem in Section II. In Section III, we discuss this problem from a compressed sensing viewpoint and introduce the equiangular tight frame fingerprint design. Using this design, we consider a detector which determines guilt for each user through binary hypothesis testing, using the correlation between the forged copy and the user's fingerprint as a test statistic. In Section IV, we derive bounds on the worst-case error probability for this detection scheme assuming a linear-average-plus-noise attack. Finally in Section V, we provide simulations that demonstrate the average-case performance in comparison to orthogonal and simplex fingerprint designs.

II. PROBLEM SETUP
In this section, we describe the fingerprinting problem and discuss the performance criteria we will use in this paper. We start with the model we use for the fingerprinting and attack processes.

A. Mathematical model
A content owner has a host signal that he wishes to share, but he wants to mark it with fingerprints before distributing. We view this host signal as a vector s ∈ R N , and the marked versions of this vector will be given to M > N users. Specifically, the mth user is given where f m ∈ R N denotes the mth fingerprint. We assume the fingerprints have equal energy: that is, D f denotes the average energy per dimension of each fingerprint. We wish to design the fingerprints {f m } M m=1 to be robust to a linear averaging attack. In particular, let K ⊆ {1, . . . , M } denote a group of users who together forge a copy of the host signal. Then their linear averaging attack is of the form where is a noise vector introduced by the colluders. We assume is Gaussian noise with mean zero and variance N σ 2 , that is, σ 2 is the noise power per dimension. The relative strength of the attack noise is measured as the watermarkto-noise ratio (WNR): This is analogous to signal-to-noise ratio. See Figure 1 for a schematic of this attack model.

B. Detection
Certainly, the ultimate goal of the content owner is to detect every member in a forgery coalition. This can prove difficult in practice, though, particularly when some individuals contribute little to the forgery, with α k 1. However, in the real world, if at least one colluder is caught, then other members could be identified through the legal process. As such, we consider s . . . focused detection, where a test statistic is computed for each user, and we perform a binary hypothesis test for each user to decide whether that particular user is guilty.
With the cooperation of the content owner, the host signal can be subtracted from a forgery to isolate the fingerprint combination: We refer to k∈K α k f k as the noiseless fingerprint combination. The test statistic for each user m is the normalized correlation function: where γ 2 is the fingerprint energy (2). For each user m, let H 1 (m) denote the guilty hypothesis (m ∈ K) and H 0 (m) denote the innocent hypothesis (m ∈ K). Letting τ denote a correlation threshold, we use the following detector: To determine the effectiveness of our fingerprint design and focused detector, we will investigate the corresponding error probabilities.

C. Error analysis
Due in part to the noise that the coalition introduced to the forgery, there could be errors associated with our detection method. One type of error we can expect is the false-positive error, whose probability is denoted P I , in which an innocent user m (m / ∈ K) is found guilty (T m (z) ≥ τ ). This could have significant ramifications in legal proceedings, so this error probability should be kept extremely low. The other error type is the false-negative error, whose probability is denoted P II , in which a guilty user (m ∈ K) is found innocent (T m (z) < τ ). The probabilities of these two errors depend on the fingerprints F = {f m } M m=1 , the coalition K, the weights α = {α k } k∈K , the user m, and the threshold τ : We will characterize the worst-case error probabilities over all possible coalitions and users.
We first define the probability of a "false alarm": This is the probability of wrongly accusing the innocent user who looks most guilty. Equivalently, this is the probability of accusing at least one innocent user. The worst-case type I error probability is given by Next, consider the probability of a "miss": This is the probability of not accusing the most vulnerable guilty user. Equivalently, this is the probability of not detecting any colluders. Note that this event is the opposite of detecting at least one colluder: The worst-case type II error probability is given by The worst-case error probability is the maximum of the two error probabilities (8) and (10): The threshold parameter τ can be varied to minimize this quantity, yielding the minmax error probability: In Section IV, we will analyze these error probabilities. We will also investigate average-case performance using simulations in Section V.

D. Geometric figure of merit
Related to the error probabilities is an important geometric figure of merit. For each user m, consider the distance between two types of potential collusions: those of which m is a member, and those of which m is not. Intuitively, if every noiseless fingerprint combination involving m is distant from every fingerprint combination not involving m, then even with moderate noise, there should be little ambiguity as to whether the mth user was involved or not.
To make this precise, for each user m, we define the "guilty" and "not guilty" sets of noiseless fingerprint combinations: In words, G is the set of combinations which do not include m. Note that in our setup (3), the α k 's were arbitrary nonnegative values bounded by one. We will show in Section IV that the best attack from the collusion's perspective uses equal weights (α k = 1 K ) so that no single colluder is particularly vulnerable. For this reason, we use equal weights to obtain bounds on the distance between these two sets, which we define to be In Section III, we find a lower bound on this distance. Another related parameter is the worst-case coherence, which is the largest inner product between any two distinct fingerprints: Intuitively, we want this value to be small, as this would correspond to having the fingerprints spaced apart. In the following section, we discuss a way of designing fingerprints which we will later evaluate using the above criteria.

III. ETF FINGERPRINT DESIGN
In this section, we introduce a fingerprint design based on equiangular tight frames (ETFs). We will discuss some important properties of ETFs and use them to determine a lower bound on the distance (12) from our geometric figure of merit. But first, we consider the fingerprinting problem from a compressed sensing viewpoint.

A. Compressed sensing viewpoint
We wish to design fingerprints in a way that will enable us to identify the small group of users who take part in a collusion. To do this, we consider a matrix-vector formulation of the attack (3) without noise, i.e., with = 0. Specifically, let F denote the N × M matrix whose columns are the fingerprints {f m } M m=1 , and let the M × 1 vector α denote the weights used in the collusion's linear average. Note that α m is zero if user m is innocent, otherwise it's given by the corresponding coefficient in (3). This gives Using this representation, the detection problem can be interpreted from a compressed sensing perspective. Namely, α is a K-sparse vector that we wish to recover. Under certain conditions on the matrix F , we may "sense" this vector with N < M measurements in such a way that the K-sparse vector is recoverable: . Suppose an N × M matrix F satisfies the restricted isometry property (RIP): for every 2K-sparse vector α ∈ R M , where δ 2K ≤ √ 2 − 1. Then for every K-sparse vector α ∈ R M , α = arg min α 1 subject to Fα = F α.
Thus, if F satisfies RIP (14), we can recover the K-sparse vector α ∈ R M by linear programming. For the attack model with adversarial noise, z = F α + , if F satisfies RIP (14), linear programming will still produce an estimateα of the sparse vector [37]. However, the distance betweenα and α will be on the order of 10 times the size of the error . Due to potential legal ramifications of false accusations, this order of error is not tolerable. Note that these methods (both for the noiseless and noisy cases) recover the entire vector α; equivalently, they identify the entire collusion. That said, we will investigate RIP matrices for fingerprint design, but to minimize false accusations, we will use focused detection (6) to identify colluders.

B. Geometric figure of merit for RIP matrices
We now investigate how well RIP matrices perform with respect to our geometric figure of merit. Without loss of generality, we assume the fingerprints are unit norm; since they have equal energy γ 2 , the fingerprint combination z can be normalized by γ before the detection phase. With this in mind, we have the following a lower bound on the distance (12) between the "guilty" and "not guilty" sets corresponding to any user m: . . , f M ] satisfy the restricted isometry property (14). Then Proof: Take K, K ⊆ {1, . . . , M } such that |K|, |K | ≤ K and m ∈ K \K . Then the left-hand inequality of the restricted isometry property (14) gives For a fixed |K|, we will find a lower bound for Since we can have |K ∩ K | > |K| 2 , we know |K|−2|K∩K | |K | < 0 when (17) is minimized. That said, |K | must be as small as possible, that is, |K | = |K ∩ K |. Thus, when (17) is minimized, we must have i.e., |K ∩ K | must be as large as possible. Since m ∈ K \ K , we have |K ∩ K | ≤ |K| − 1. Therefore, Substituting (18) into (16) gives Since this bound holds for every m, K and K with m ∈ K\K , we have (15). Note that (15) depends on δ 2K , and so it's natural to ask how small δ 2K can be for a given fingerprint design. Also, which matrices even satisfy RIP (14)? In general, we say F is (K, δ)-RIP if for every K-sparse vector x, Proving that a given matrix F is (K, δ)-RIP involves calculating eigenvalues of all size-K submatrices, which is computationally difficult for large matrices. The following lemma makes this explicit: Proof: We first note that F being (K, δ)-RIP trivially implies that F is (K, δ + )-RIP for every > 0. It therefore suffices to show that (i) F is (K, δ min )-RIP, and (ii) F is not (K, δ)-RIP for any δ < δ min . To this end, pick some K-sparse vector x. To prove (i), we need to show that Let K ⊆ {1, . . . , M } be the size-K support of x, and let x K be the corresponding subvector. Then rearranging (20) gives Since, by definition, δ min maximizes (21) over all supports K and entry values x K , the inequality necessarily holds; that is, F is necessarily (K, δ min )-RIP. Furthermore, equality is achieved by the support K which maximizes (19) and the eigenvector x K corresponding to the largest eigenvalue of F * K F K − I K ; this proves (ii).
Since calculating eigenvalues for all size-K submatrices is computationally difficult, the Gershgorin circle theorem is often used to obtain a coarse bound in demonstrating RIP: Theorem 4 (Gershgorin circle theorem [38]). Take a K × K matrix A. Then for each eigenvalue λ of A, there exists an i ∈ {1, . . . , K} such that λ lies in the complex disk centered at A ii of radius j =i |A ij |.
This leads to the following well-known bound on δ 2K in terms of worst-case coherence: Lemma 5. Given a matrix F with unit-norm columns, then where µ is the worst-case coherence (13).
Proof: From Lemma 3, the optimal δ 2K is In words, given an ensemble of fingerprints, we consider each subcollection of size 2K, subtract the identity from their 2K ×2K Gram matrix and calculate the largest eigenvalue; the largest eigenvalue we find over all subcollections is what we call δ 2K . Since the fingerprints have unit norm, every Gram matrix of 2K fingerprints will have ones on the diagonal, and the absolute values of the off-diagonal entries will be no more than µ. Therefore, by applying the Gershgorin circle theorem (Theorem 4) to δ 2K , we obtain (22). Combining Theorem 2 and Lemma 5 yields a coherencebased lower bound on the distance between the "guilty" and "not guilty" sets corresponding to any user m: We would like µ to be small, so that the lower bound (23) is as large as possible. But for a fixed N and M , the worstcase coherence of unit-norm fingerprints cannot be arbitrarily small; it necessarily satisfies the Welch bound [39]: Equality in the Welch bound occurs precisely in the wellstudied case where the fingerprints form an equiangular tight frame (ETF). An equiangular tight frame is a N × M matrix which has orthogonal rows of equal norm and unit-norm columns whose inner products have equal magnitude [40]. One type of ETF has already been proposed for fingerprint design: the simplex [20]. The simplex is an ETF with M = N + 1 and µ = 1 N . In fact, [20] gives a derivation for the value of the distance (12) in this case: The bound (23) is lower than (24) by a factor of 1 − 2K N +1 , and for practical cases in which K N , they are particularly close. Overall, ETF fingerprint design is a natural generalization of the provably optimal simplex design of [20].

C. Existence of RIP matrices
We now discuss the existence of RIP matrices as well as the construction of a specific class of ETFs. Given the RIP definition (14), it might not be clear how many matrices satisfy this condition. Surprisingly, RIP matrices are abundant; for any δ 2K , there exists a constant C such that if N ≥ CK log(M/K), then matrices of Gaussian or Bernoulli (±1) entries satisfy RIP with high probability. However, as mentioned in the previous section, checking if a given matrix satisfies RIP is computationally difficult.
Fortunately, there are some deterministic constructions of RIP matrices, such as [41], [42]. However the performance, measured by how large K can be, is not as good as the random constructions; the random constructions only require Fig. 2. The equiangular tight frame constructed in Example 1. N = Ω(K log a M ), while the deterministic constructions require N = Ω(K 2 ). The specific class of ETFs additionally requires M ≤ N 2 [40].
Whether N scales as K versus K 2 is an important distinction between random and deterministic RIP matrices in the compressed sensing community. However, this difference offers no advantage for fingerprinting. Ergun et al. showed that for any fingerprinting system, a collusion of K = O( N/ ln N ) is sufficient to overcome the fingerprints [18]. This means with such a K, the detector cannot, with high probability, identify any attacker without incurring a significant false-alarm probability P fa (7). This constraint is more restrictive than deterministic ETF constructions, as N/ ln N < √ N N/ log a M . Consequently, random RIP constructions are no better for fingerprint design than deterministic constructions.
Ergun's bound indicates that with a large enough K, colluders can overcome any fingerprinting system and render our detector unreliable. We now show that if K is sufficiently large, the colluders can exactly recover the original signal s: Lemma 7. Suppose the real equal-norm fingerprints {f k } k∈K do not lie in a common hyperplane. Then s is the unique minimizer of Proof: Note that g(x) ≥ 0, with equality precisely when x − (s + f k ) 2 is constant over k ∈ K. Since the f k 's have equal norm, g(s) = 0. To show that this minimum is unique, suppose g(x) = 0 for some x = s. This implies that the values x − (s + f k ) 2 are constant, with each being equal to their average. Moreover, since we have that x − s, f k is constant over k ∈ K, contradicting the assumption that the fingerprints {f k } k∈K do not lie in a common hyperplane.

D. Construction of ETFs
Having established that deterministic RIP constructions are just as good as random constructions for fingerprint design, we now consider a particular method for constructing ETFs. Note that ETFs are notoriously difficult to construct in general, but a relatively simple approach was recently introduced in [42]. The approach uses a tensor-like combination of a Steiner system's adjacency matrix and a regular simplex, and it is general enough to construct infinite families of ETFs. We illustrate the construction with an example: Example 1 (see [42]). To construct an ETF, we will use a simple class of Steiner systems, namely (2, 2, v)-Steiner systems, and Hadamard matrices with v rows. In particular, (2, 2, v)-Steiner systems can be thought of as all possible pairs of a v-element set [43], while a Hadamard matrix is a square matrix of ±1's with orthogonal rows [43].
In this example, we take v = 4. The adjacency matrix of the (2, 2, 4)-Steiner system has 4 2 = 6 rows, each indicating a distinct pair from a size-4 set: To be clear, we use "+/−" to represent ±1 and an empty space to represent a 0 value. Also, one example of a 4 × 4 Hadamard matrix is We now build an ETF by replacing each of the "+" entries in the adjacency matrix (25) with a row from the Hadamard matrix (26). This is done in such a way that for each column of A, distinct rows of H are used; in this example, we use the second, third, and fourth rows of H. After performing this procedure, we normalize the columns, and the result is a real ETF F of dimension N = 6 with M = 16 fingerprints (see Figure 2).
We will use this method of ETF construction for simulations in Section V. Specifically, our simulations will let the total number of fingerprints M range from 2N to 7N , a significant increase from the conventional N + 1 simplex and N orthogonal fingerprints. Note, however, that unlike simplex and orthogonal fingerprints, there are limitations to the dimensions that admit real ETFs. For instance, the size of a Hadamard matrix is necessarily a multiple of 4, and the existence of Steiner systems is rather sporadic. Fortunately, identifying Steiner systems is an active area of research, with multiple infinite families already characterized and alternative construction methods developed [42], [44].

A. Analysis of type I and type II errors
We now investigate the worst case errors involved with using ETF fingerprint design and focused correlation detection under linear averaging attacks. Recall that the worst-case type I error probability (8) is the probability of falsely accusing the most guilty-looking innocent user. Also recall that the worstcase type II error probability (10) is the probability of not accusing the most vulnerable guilty user.
Theorem 8. Suppose the fingerprints F = {f m } M m=1 form an equiangular tight frame. Then the worst-case type I and type II error probabilities, (8) and (10), satisfy Proof: Under hypothesis H 0 (m), the test statistic for the detector (6) is where is the projection of noise /γ onto the normed vector f m /γ, and, due to symmetry of the variance of in all dimensions, ∼ N (0, σ 2 /γ 2 ). Thus, under hypothesis H 0 (m), T z (m) ∼ N ( n∈K α n (±µ), σ 2 /γ 2 ). We can subtract the mean and divide by the standard deviation to obtain: Note that Q(x) is a decreasing function. The bound (27) is obtained by setting all of the coefficients of the coherence to be positive. Likewise, under hypothesis H 1 (m), the test statistic is Thus, under hypothesis H 1 (m), Since 1 − Q(x) = Q(−x), the type II error probability can be bounded as We can now evaluate the worst-case errors (8) and (10). For type I errors, with m / ∈ K: For type II errors, The last equation follows since once the α's are fixed, the actual coalition K does not matter. We can further maximize over all possible weightings α: Thus, the vector α which minimizes the value of its maximum element is the uniform weight vector. This motivates the attackers' use of a uniformly weighted coefficient vector α to maximize the probability that none of the members will be caught.

B. Minimax error analysis
From a detection standpoint, an important criterion is the minimax error probability (11). The threshold τ trades off type I and type II errors. Thus, there is a value of τ , denoted by τ * , which minimizes the maximum of the probabilities of the two error types. Since the bound for the type I error probability is independent of α, and the bound for the type II error probability is maximized with a uniform weighting, assume this to be the case.
Theorem 9. The minmax probability of error (11) can be bounded as: where Note that for orthogonal and simplex fingerprints, the minmax errors are both of the form For orthogonal fingerprints [20], which is better than d * low (K) (the Q function is decreasing). For simplex fingerprints, d * (K) is slightly better than both [20]: Proof: The lower bound is the sphere packing lower bound [24]. For the upper bound, P e (F, τ, α) = max{P I (F, τ, α), P II (F, τ, α)} Since the test statistic T z (m) is normally distributed with the same variance under either of the hypotheses H 0 (m) and H 1 (m), the value of τ that minimizes this upper bound is the average of the means µ and 1+µ K − µ, namely τ * := 1+µ 2K . Using this τ * and recalling (2), we have P minmax (F, α) = min τ P e (F, τ, α) = P e (F, τ * , α) Consider the regime where N is large, M grows linearly or faster than N , and WNR is constant (in particular 0, so D f = σ 2 ). Then µ ≈ 1/ √ N , If K √ N , then both bounds go to infinity so P minmax (F, α) → 0. Also, the geometric figure of merit (12) then behaves as If K is proportional to √ N , then P minmax (F, α) is bounded away from 0.
We can also compute the error exponent for this test: Corollary 10. If M N K 2 , then the error exponent is Proof: The proof follows by applying the asymptotic equality ln Q(t) ∼ − t 2 2 as t → ∞ to the bounds in (28). The bounds are asymptotically equivalent.
Note that this error exponent is the same as in the simplex case [20]. As K → ∞, the error exponent (29) goes to zero.

V. SIMULATIONS
In Section IV, the worst-case error probabilities were analyzed, where the worst case was over all collusions. Here we investigate average case behavior. We examine the probability of detecting at least one guilty user, P d (9), as a function of K with the false-alarm P fa (7) fixed below a threshold. The threshold can be interpreted as the (legally) allowable limit for probability of false accusation. We compare the average case performance of ETF fingerprints, simplex fingerprints [20], and orthogonal fingerprints [16] for four dimension sizes N ∈ {195, 651, 2667, 8128}. The ETF construction described in Example 1 was used. The results demonstrate that ETF fingerprints perform almost as well as both orthogonal and simplex fingerprints, while accommodating several times as many users. We now describe the design of the simulations.
The orthogonal fingerprint design was constructed using an identity matrix. For actual embedding, the orthogonal fingerprints should be randomly rotated to ensure difficulty in removing them. One method to achieve this is to randomly generate i.i.d. Gaussian vectors in N dimensional space, orthogonalize them, then scale them to have the same energy [16]. For detection purposes, however, rotations of the basis vectors are inconsequential.
The simplex fingerprint design was constructed using the following method of sequentially fixing the values of the fingerprints in each dimension. The vectors of a regular simplex are equidistant from the center, having the same power, and have inner products equal to − 1 N [45]. Letting the first vector have a one in the first row and zeros in the other rows forces every other vector's first element to be − 1 N to satisfy the inner product constraint. For the second vector, choose its second element to satisfy the power constraint and set the elements of the remaining rows to zero. Using the inner product constraint, we can find the value of the second element for all other vectors. Repeating these steps constructs a regular simplex.
Linear collusion attacks were simulated separately for the different designs and collusion sizes K. For each attack, K of the M fingerprints were randomly chosen and uniformly averaged. Next, an i.i.d. Gaussian noise vector was added with per-sample noise power σ 2 = D f , corresponding to a WNR (4) of 0 dB [19].
The test statistics T z (m) (5) were then computed for each user m. For each threshold τ , it was determined whether there was a detection event (at least one colluder with T z (m) > τ ) and/or a false alarm (at least one innocent user with T z (m) > τ ). In total, 50,000 attacks were simulated, and the detection and false alarm counts were averaged. Then the minimal τ value was selected for which P fa ≤ 10 −3 . This induced the corresponding P d .

B. Results
We ran experiments with four different dimension sizes N ∈ {195, 651, 2667, 8128}. The noise level was kept at WNR = 0 dB. The value of K varied between 1 and sufficiently large values so P d approached zero. Plots for the probability of detection P d as a function of the size of the coalition K are shown in Figures 3-6 for N ∈ {195, 651, 2667, 8128} respectively. The largest values of K for which at least one attacker can be caught with probability (nearly) one under the P fa constraint are about 2, 5, 11, and 21 respectively. Overall, ETF fingerprints perform comparably to orthogonal and simplex fingerprints while accommodating many more users. Fig. 3. A plot of the probability of detecting at least one colluder (P d ) as a function of the number of colluders (K). The threshold τ is picked to be the minimum threshold to fix P fa ≤ 10 −3 . The WNR is 0 dB and N = 195. The (maximum) number of fingerprints were 195 for the orthogonal, 196 for the simplex, and 1456 for the ETF construction. Fig. 4. A plot of the probability of detecting at least one colluder (P d ) as a function of the number of colluders (K). The threshold τ is picked to be the minimum threshold to fix P fa ≤ 10 −3 . The WNR is 0 dB and N = 651. The (maximum) number of fingerprints were 651 for the orthogonal, 652 for the simplex, and 2016 for the ETF construction. Fig. 5. A plot of the probability of detecting at least one colluder (P d ) as a function of the number of colluders (K). The threshold τ is picked to be the minimum threshold to fix P fa ≤ 10 −3 . The WNR is 0 dB and N = 2667. The (maximum) number of fingerprints were 2667 for the orthogonal, 2668 for the simplex, and 8128 for the ETF construction. Fig. 6. A plot of the probability of detecting at least one colluder (P d ) as a function of the number of colluders (K). The threshold τ is picked to be the minimum threshold to fix P fa ≤ 10 −3 . The WNR is 0 dB and N = 8128. The (maximum) number of fingerprints were 8128 for the orthogonal, 8129 for the simplex, and 16, 384 for the ETF construction.