WO2008084482A2

WO2008084482A2 - Finite harmonic oscillator

Info

Publication number: WO2008084482A2
Application number: PCT/IL2008/000046
Authority: WO
Inventors: Ronny Hadani
Original assignee: Gurevich, Shamgar
Priority date: 2007-01-10
Filing date: 2008-01-10
Publication date: 2008-07-17
Also published as: WO2008084482A3

Abstract

A dictionary at least partially spans a set of discrete q-length signals. The atoms of the dictionary are eigenvectors of a representation of a commutative subgroup of a finite symplectic group. The dictionary may be used for interpreting a radar signal, denoising a signal, compressing data, finding a sparse representation, deblurring at a signal, finding a sparse representation of a signal, encoding a signal for communication, encoding a symbol for CDMF communication, classifying a data set and generating a random number.

Description

FINITE HARMONIC OSCILLATOR

FIELD AND BACKGROUND OF THE INVENTION

Various methods and systems to generate a dictionary for coding and decoding signals are possible, and particularly, methods and systems may produce a large dictionary of atoms having the desirable properties of weak mutual coherence, weak autocorrelation and a small supremum (the supremum is sometimes referred to as the peak-to-average power ratio).

Digital signals, or simply signals, can be thought of as functions of a finite number of elements. The elements may be spaced along a line (single-dimensional), along a plane (two-dimensional) in space (three-dimensional) or in a hyper-space (multi dimensional). For example, in one-dimension we will consider Fq the finite line namely the finite field with q elements indexed by time t. The space of signals H = C(Fq) is a Hubert space equipped with a natural Hermitian product

(φ,φ) = Σ φ(t)φ(t) for two signals ώ, ωe H. v ' feF, ^v ' ^v '

A central problem is constructing useful classes of signals that demonstrate strong descriptive power and at the same time are characterized by formal mathematical conditions. Meeting these two requirements is a non-trivial task and is a source for many novel developments in the field of signal processing. The problem was tackled, over the years, by various approaches. In the classical approach, a signal is characterized in terms of its expansion with respect to a specific basis. A standard example of this kind is the class of limited band signals, which is defined using the Fourier basis and consists of signals with a specified support of their Fourier representation.

However, for certain applications this approach is too restrictive. In a more general approach, the signal is characterized in terms of its expansion with respect to a frame, which is kind of a generalized basis. The theory of wavelets is a particular application of this approach (see US patent 7,272,599 issued to Gilbert, et al.). As it turns out, many classical results from linear algebra have appropriate generalizations to the setting of frames, as a consequence, wavelets analysis exhibit structural similarity to Fourier analysis.

Recently, (e.g. US patent 7,271,747 issued to Baraniuk, et al.) a novel approach was introduced, hinting towards a fundamental change of perspective about the nature of signals. This new approach uses the notion of a dictionary, which is yet another kind of generalized basis. The basic idea is the same as before, namely, a signal is characterized in terms of its expansion as a linear combination of vectors in the dictionary. Each vector in the dictionary is called an atom. The main difference is that the characterization is intrinsically non-linear, hence as a consequence, one comes to deal with classes of signals which are not closed with respect to addition. More formally a dictionary is a set D of atoms S₁ (in some of the literature listed herein [e.g. Gurevich, S., "Weil Representation, Deligne Sheaf and Proof of the Kurlberg-Rudnick Conjecture", Thesis submitted for the degree "Doctor of Philosophy" University of Tel-Aviv, available at arXiv:math-ph/0601031 vl 15 Jan 2006] the dictionary D is referred to as a system S and the atoms are referred to as signals) for the sake of discussion herein the symbols D and D are the same and the symbols F₉ and Fq are the same.

A very simple example of a dictionary 110 is illustrated in Figure 1. Dictionary 110 may be thought of as a matrix having L columns each column being an atom 5", 115a-v, which is a ^-length vector. In the example of Figure 1, q=l l and L=22. A signal 120 (which can be thought of as a ^-length vector) is the product of dictionary 110 and a vector of coefficients 130. The rank of dictionary 110 and the length of vector 120 are q. Necessarily, q ≤L. The atoms are normalized i.e. kS,k₂= 1. It is clear that if q<L a single signal may be represented in more than one way and thus coefficients a_\...aι are not unique. One idea is to find the sparsest possible representation of ψ = ∑a_sS (sparse meaning having few non-zero coefficients).

SeD

In the example of Figure 1 atoms 115a-k (S⁵ _O through S^₁₀) are the standard basis Of F₁₁ i.e. S^S _j=δ(t-τ_J) for τ,2F_n i.e. X₁ = {0,1,2,3...10}. Atoms 1151-v (S^₀ through S^₀) are the Fourier basis Sf_j=q^~mexp(i2 πωβ/q) where i is the square root of -1 and CO_j, t_j 2 F_g and as stated before in the example of Figure I , q= 11. Clearly each basis S⁵, (atoms 115a-k) and S_j (atoms 1151-v) span Fn. Therefore the coefficient vector (αi,..., Or₂₂) is not unique: We can express a vector ψ in many ways. For example in Figure 2a a signal 220a ψ=a._\δ(t-4)+ aιq^'mcos(2π3t/q) is illustrated in terms of the standard basis (thus each asterisk in the Figure 2a,b represents the value of the coefficient α, for /={0,1,2,3,...,10} given by the x-axis and α/=0 for /={11,12,13...21 }. Alternatively, in Figure 2b we can express the signal 220b ψ in the Fourier basis. The Fourier transform of ψ is ψr{f) = a_ιq^~υ2 cos(2πτf / q)+ a₂δ(f - ω) , thus the to express ψ in the Fourier basis we set 0₀...,O₁₀=O and set a._{\ \} ...,aι- _\ the numbers shown by the asterisk in Figure 2b. In either case (the coefficients of the standard basis in Figure 2a or of the Fourier basis Figure 2b) representing signal 220a,b ψ requires 11 non-zero coefficients. On the other hand using our entire dictionary 110 we find that ψ=<x_\8 ^! ₅+α₂5 ^ and thus can be represented by the coefficient vector {0,0,0,0,ai,0,0,0,0,0,0,0,0,0,0,a₂,0,0,0,0,0,0}. Finding this sparse representation has great value in signal analysis (for example in Code Division Multiple Access CDMA if two transmitters are transmitting simultaneously, the coefficients of the sparse representation are the clean signals of each of the transmitters; similarly in data compression, the sparse representation is the most efficient way to store the data). The obvious goal then is to find the largest possible dictionary from which we can find a unique sparse representation of a large class of signals.

The first question that needs to be addressed is, given a representation of a signal, whether it is the sparsest representation or is there an alternative sparse or sparser representation. The mathematical tools to answer this question are as follows. The dictionary D is called an N -independent set if every subset D'czD, with N elements jD'j=N, is linearly independent. Given a 2N-independent set D, every signal y/2H, has at most one representation of the form ψ = ∑ a_sS . D'cz D, with jD'j≤N. Such a

SeD¹ representation, if exists, it is unique and is called the sparse representation. Consequently another name for such a set D is an N-sparse dictionary. Given that a signal ψ admits a sparse representation, it is natural to ask whether the coefficients as can be effectively reconstructed. A dictionary D for which there exists a polynomial time algorithm for reconstructing the "sparse" coefficients is called an effectively N- sparse dictionary. As an example in CDMA if one has an effectively N-sparse dictionary with q³ atoms, one can assign a separate code to q³ users and at any given time and place as many as N users may simultaneously transmit without significant interference.

To give some feeling for the new concept, we note that an orthonormal basis appears as a degenerate example of an effectively sparse dictionary. More precisely, it is dimH-sparse, consisting of dimH atoms. The effectiveness follows from the fact that the coefficient a_s can be reconstructed from a signal ψ by as = hS; yλ.

A basic problem in the new theory is introducing systematic constructions of "good" effectively N-sparse dictionaries. Here "good" means that the size of the dictionary and the sparsity factor N are made as large as possible. Currently, the only known methods use either certain amount of randomness or are based on ad-hoc considerations.

Showing that a dictionary is effectively N-sparse is difficult. A way to overcome this difficulty is to introduce the stronger notion of weakly correlated dictionaries. A dictionary D is called "-correlated for 0 < " « 1 if for every two different atoms S,≠S_j 2 D we have jhS^ij < ". The two notions of correlation and sparsity are related by the following proposition: IfD is l/i?-correlated then D is effectively i?/2-sparse.

The final question is whether it is possible to find the sparse representation. The tools to answer this question are also available in mathematics. In general if there

exists a representation of a signal ψ = Σ afi such that N<(2^{A 2}-0.5)/μ where μ is the

maximum cross-co variance

then the representation is unique and can be found using known minimization and optimization routines that are commercially available for example in MATLAB® matrix operation package and particularly using the signals and optimization toolboxes (more details on this are available in the manual to MATLAB® and in the literature for example see Tropp, J. A., Just Relax: Convex Programming Methods for Identifying Sparse Signals in Noise, IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 52, NO. 3, pp 1030-1051, MARCH 2006)

Thus, given a dictionary D, there are various desired properties which appear in the engineering wish list [e.g. see Howard, S. D.; Calderbank, A. R.; Moran, W. "The finite Heisenberg-Weyl groups in radar and communications". EURASIP JOURNAL ON APPLIED SIGNAL PROCESSING Art. No. 85685 2006 (2006); Golomb S.W. and Gong G., Signal design for good correlation. For wireless communication, cryptography, and radar. Cambridge University Press, Cambridge (2005); W. Miller, "Topics in harmonic analysis with applications to radar and sonar," in Radar and Sonar, Part I, R. Blahut, W. Miller, and C.Wilcox, Eds., IMA Volumes in Mathematics and Its Applications, Springer, New York, NY, USA, 1991; L. Auslander and R. Tolimieri, "Radar ambiguity functions and group theory," SIAM Journal on Mathematical Analysis, vol. 16, no. 3, pp. 577-601, 1985; M. S. Richman, T. W. Parks, and R. G. Shenoy, "Discrete-time, discrete-frequency, time-frequency analysis," IEEE Transactions on Signal Processing, vol. 46, no. 6, pp. 1517-1527, 1998.]. For example, in various situations one requires that the atoms will be weakly cross-correlated, i.e., that for any two atoms Si 6= Sj 2 D J(S₁; S, )j«1 ; this property is trivially satisfied if D is an orthonormal basis. Such a system cannot consist more then dimH atoms, however, for certain applications, [e.g., CDMA as explained by Viterbi AJ., CDMA: Principles of Spread Spectrum Communication. Addison-Wesley Wireless Communications (1995).] a larger number of atoms is desired, in that case the orthogonality condition is relaxed.

During the transmission process, an atom S might be distorted in various ways. Two basic types of distortions are time shift S(t) 7! L_τS(t) = S(t + τ) and phase shift S(t) 7! M_ωS(t) = exp(2πiωt/q) S(t), where τ; ω 2 Fq. The first type appears in asynchronous communication and the second type is a Doppler effect due to relative velocity between the transmitting and receiving antennas, hi conclusion, a general distortion is of the type S 7! M_ωL_τS; suggesting that for every S, 6= S₇ 2 D it is natural to require the following stronger condition that both the autocorrelation and the cross correlation for all atoms under a general distortion be small j<S,; M_ωL_τS,)j«1 for all ω ,τ2 Fq and for all S₁, S_j 2 D (that is to say whether i =j or z^'6=y^"): Also in radar from the time translation of a reflected signal it is possible to identify the distance to the target and from the frequency modulation of the reflected signal it is possible to determine the speed at which the target is approaching/being approached. Thus in radar it is desirable to have a system that is sensitive to these distortions so that by optimization one can determine the distortion and thus location and velocity of the target.

Due to technical restrictions in the transmission process, signals are sometimes required to admit low peak-to-average power ratio [for an explanation of this requirement see Paterson, K. G. and Tarokh V., "On the existence and construction of good codes with low peak-to-average power ratios". IEEE Trans. Inform. Theory 46 (2000).], i.e., low peak-to-average power ratios means that for every normalized 52 D max fjSrøj : 12 F_Pg « 1 (normalized means that kSk₂ = 1 ):

Finally, several schemes for digital communication require Fourier invariance, which means that the above properties will continue to hold also if we replace atoms from D by their Fourier transform:

To find a dictionary that spans a signal space and has the desired properties, it is necessary to use a few results from representation theory. A group is a set of elements and a multiplication rule such that the set is closed under multiplication, a neutral element with respect to the multiplication belongs to this set and that for each element its inverse belongs to the set. An example is the set of unitary operators on the Hubert space of functions over the finite field F_q where q is a power of a prime number {a unitary operator acts on a member of the Hubert space and assigns it to another member of the Hubert space}. We denote the Hubert space by H(F₉), and the group of unitary operators on that Hubert space by U(H(F_g)). The multiplication is the composition. In a given coordinate system these operators are q£q matrices and the multiplication is the usual matrix multiplication. An Abelian group is a commutative group gigr= gig_\- An Abelian subgroup of U(H(F₉)) can be diagonalized together by a single set of eigenvectors S, . These eigenvectors span the Hubert space.

An example of an Abelian group is the set of time shifts L(τ,) [L(τ,) is the same as L₁ above] for all τ,eF_q where L(X₁)S₁(I)=S₁^x₁). It is clear that time shifting is commutative {L(xι)L(x₂)S,(t)=L(x₂)L(x_\)S,{t)}. The Abelian group of time shifts may be written as a q£q matrix where the (j,k) matrix element is (Z(τ,))_jk=δ (τ_j-X_k+τ,) where δ (x) = 1 if x=0 mod q and 0 otherwise. The eigenvectors of this matrix are the vectors ^<f~q^~l/2exp(i2 πω,t/q) that we defined previously because

where λ,(τ)= q^~mexp(i2πω_jx/q). Similarly the group of frequency modulations M(ω)S',(t) = eκp(2πiωt/q) S,(t) has as its eigenvectors the vectors

because M(ω)S",(t) = λ_j(ω)S^(t) where λ_j(ω)=^^"1/2exp(/2 πan/q) [the terminology M(ω) and M_ω refer to the same frequency shift].

Continuous Heisenberg-Weyl groups have long been applied to interpret radar signals [e.g. see US patent 5831934 issued to Gill et al.; W. Miller, "Topics in harmonic analysis with applications to radar and sonar," in Radar and Sonar, Part I, R. Blahut, W. Miller, and C.Wilcox, Eds., IMA Volumes in Mathematics and its Applications, Springer, New York, NY, USA, 1991; L. Auslander and R. Tolimieri, "Radar ambiguity functions and group theory," SLAM Journal on Mathematical Analysis, vol. 16, no. 3, pp. 577-601, 1985]. More recently it has been suggested that finite Heisenberg-Weyl groups could be useful building a dictionary for digital radar and communication [Howe R., "Nice error bases, mutually unbiased bases, induced representations, the Heisenberg group and finite geometries". Indag. Math. (N.S.) 16: no. 3-4, 553.583 (2005); Howard, S. D.; Calderbank, A. R.; Moran, W. "The finite Heisenberg-Weyl groups in radar and communications". EURASIP JOURNAL ON APPLIED SIGNAL PROCESSING Art. No. 85685 2006 (2006).]

The Heisenberg dictionary DH is constructed using the representation theory of the finite Heisenberg group. For a digital signal having q elements the Heisenberg dictionary contains of the order of q² atoms and is q^'m correlated.

To form the Heisenberg dictionary rather than taking separately frequency modulations and time translations (making a dictionary having Iq atoms as in the example of Figures 1, 2a and 2b), the translation and modulations are conjugated. This conjugation produces 2D qxq array of combinations of time translations and frequency modulations. It is not trivial to make a homomorphism from the time frequency plane F_q*Fq that consists of q couples (τ,ω) to unitary operators on a the corresponding Hubert space of ^-dimensional signals. There is nevertheless a well known homomorphism π(τ,ω,z)=exp[(πzτω+2z_y)/g)M_ωL_τ with the group law (τi,ωi,zi)»(τ₂,ω_2r-:₂)⁼(^τi^+τ ₂, ωi+ω_2r2i+Z₂+(τiω₂-τ₂ωi)/2). As stated above, a set of unitary operators can be found spanning an Abelian group (a set with a commutative multiplication law). The Heisenberg group law is not commutative because (τ₁ω₂-τ₂ω₁)≠(τ₂ω₁-τ₁ω₂). Nevertheless, for a subgroup of the Fq A- Fq plane where T₂CD₁-T₁(O₂=O the law is commutative. Furthermore, for a given τ₂,ω₂ then the law is commutative along the line

through the origin. More generally, any line through the origin is a commutative subspace in the Heisenberg representation. Therefore, we can choose a set of (#+1) lines through the origin and on each of those lines choose a set of q eigenvectors and the total set of all q(q+l) eigenvectors forms a Heisenberg dictionary that spans the entire Hubert space of signals. As it turns out, the Heisenberg dictionary has the following properties: The dictionary has q(q+l) signals. The autocorrelation is 1 for modulation/translation that is a characteristic function of a line passing through the origin (an Abelian subgroup of the Heisenburg representation) 0 otherwise. The cross correlation is 1 for two signals on a line passing through the origin and zero otherwise. The supremum is q^{Λ 2}. Thus it is possible to identify the line through the origin in the time/frequency plane to which the signal belongs. This is useful but not optimal in radar because it is difficult to determine the location and the velocity of a target independently. Similarly in communication this leads to interference between some signals of the system. The ambiguity function is a measure of signal interference (or specificity of identification for radar). Thus the ambiguity function of the Heisenberg system (illustrated in Figure 3) instead of sharp peak has a linear ridge along a line crossing the origin. It is preferable to have a symmetric peak, thus for example US patent 6278686 issued to Alard reveals a method to reshape an ambiguity function to achieve symmetry.

There is thus a widely recognized need for, and it would be highly advantageous to have a large dictionary of atoms having the desirable properties of a small normalized peak-to-average power ratio, weak cross correlation (both of pure atoms and of atoms that have undergone time translation or frequency modulation), and weak autocorrelation under time translation or frequency modulation.

SUMMARY OF THE INVENTION

Various methods and systems to produce a dictionary of atoms are possible, and particularly, methods and systems may employ a Weil representation of a commutative subgroup of a finite symplectic groups and atoms of the dictionary may be the eigenvectors of the Weil representation.

An embodiment of a dictionary at least partially spanning a set of discrete ^-length signals may include a representation of a commutative subgroup of a finite symplectic group, and may also include a plurality of atoms wherein each of the atoms is an eigenvector of the representation.

In the dictionary the symplectic group may be a n-dimensional matrix Sp(M₁F₉).

In the dictionary there may be at least q (q + 1) +1 atoms.

In the dictionary the atoms may have one of the verifiable properties of a normalized peak-to-average power ratio of less the inverse of the square root of q (PMPR < q^An), an autocorrelation under frequency modulation of less than 2

e D₀, ω ≠ 0), an autocorrelation under time translation of less than 2q^~l (q+l)(q-l) ^}

(\(φ,L_τφ)\≤ 2(q + lXq-iy^λq^'V2Vφe O₀,r≠ 0 ) or a cross correlation of less than

≤4q-^υ2Vτ,ω ε F_q andφ,φ e D₀ ). At least one of these properties may be invariant under one of the following operations a Fourier transform, a quadratic modulation or a homothety.

A dictionary may also include a minimization procedure for extracting a sparse representation of at least one of the signals in terms of at least one atom from the plurality of atoms. hi the dictionary the symplectic representation may be a Weil representation.

The dictionary may be applied to one of the following tasks interpreting a radar signal, denoising at least one of the signals, compressing data, finding a sparse representation, deblurring at least one of the signals, finding a sparse representation of one of the signals, encoding a symbol for communication, encoding at least one symbol for CDMA or OFDM communication, classifying a data set and generating a random number.

An embodiment of a method of producing a dictionary at least partially spanning a set of discrete ^-length signals may include the following steps: defining a representation of a commutative subgroup of a finite symplectic group, and specifying a plurality of atoms wherein each of the plurality of atoms is an eigenvector of the representation.

In the method of producing a dictionary, the symplectic group may be Sp(2n,F_q).

In the method of producing a dictionary, there may be least q (q + 1) +1 atoms.

In the method of producing a dictionary, the verifiable properties of the atoms may include a normalized peak-to-average power ratio of less the inverse of the square root of q (PMPR < q^'m), an autocorrelation under frequency modulation of less than 2?^"1/2(9+l)/(9-l) (|{^,M^)| < 2(₉ + lX_? M)^~V^1/2v<?> e G₀,ω ≠ () ), an autocorrelation under time translation of less than

e G₀,τ ≠ 0) or a cross correlation of less than

4fø+l)fø-l)^'Y^1/2

<4q-^mV τ,ω e F_q andφ <Ξ G₀ ). One or more of the above properties may be invariant under one or more of the operations of a Fourier transform, a quadratic modulation and a homothety.

The method of producing a dictionary may also include the step of extracting a sparse representation of at least one of the signals in terms of at least one of the atoms.

In the method of producing a dictionary, the representing may be via a Weil representation.

The method of producing a dictionary may further include the step of applying the dictionary to one of the following tasks interpreting a radar signal, denoising at least one of the signals, compressing data, finding a sparse representation, deblurring at least one of the signals, finding a sparse representation of at least one of the signals, encoding a symbol for communication, encoding at least one symbol for CDMA or OFDM communication, classifying a data set and generating a random number.

An embodiment of a method to interpret a radar signal may include the steps of providing a plurality of atoms which at least partially span a set of signals and determining a time shift of an echo of at least one of the signals. Each of the atoms may be an eigenvector of a representation of a commutative subgroup of a finite symplectic group.

The method to interpret a radar signal may also include: resolving a frequency modulation of the echo.

An embodiment of a method to acquire a sparse representation of a signal may include the steps of providing a plurality of atoms and determining a sparse representation of the signal in terms of the atoms. The atoms may at least partially span the signal and each of the atoms may be an eigenvector of a representation of a commutative subgroup of a finite symplectic group.

An embodiment of a method of communication using a set of signals may include the steps of providing a plurality of atoms and encoding at least one of the signals using at least one of the atoms. The atoms may at least partially span the signals and each of the atoms may be an eigenvector of a representation of a commutative subgroup of a finite symplectic group.

BRIEF DESCRIPTION OF THE DRAWINGS

Various embodiments of a system and method to generate a dictionary for coding and decoding signals are possible, and are herein described, by way of example only, with reference to the accompanying drawings, where:

Figure 1 is an illustration of a previous art dictionary;

Figure 2 is an illustration of two alternative non-sparse representations of a signal in terms of the dictionary illustrated in Figure 1 ;

Figure 3 is a graph of an ambiguity function for a Heisenberg dictionary;

Figure 4 is a flowchart of a method of CDMA communication using a Weil dictionary;

Figure 5 is a graph of an ambiguity function for a CDMA pseudo noise dictionary;

Figure 6 is a graph of an ambiguity function for a Weil dictionary;

Figure 7 is a s a flowchart of a method of interpreting radar using a Weil dictionary;

Figure 8 is a flowchart of an embodiment of a method of producing a Weil dictionary.

DESCRIPTION OF THE PREFERRED EMBODIMENTS

The principles and operation of a system and method to generate a dictionary for coding and decoding signals, and particularly, a method and system for producing a large dictionary of atoms having the desirable properties of weak mutual coherence, cross-correlation, weak autocorrelation and a small supremum according to various embodiments may be better understood with reference to the drawings and the accompanying description.

Attention is called to Figure 4, which is a flow chart illustrating use of the Heisenberg- Weil dictionary for CDMA communication (Note that some authors label the Heisenberg group described in the background section as a Heisenberg- Weyl groups. This is not the same as the Heisenberg- Weil dictionary described herein below). The first step is to generate a large Weil dictionary 410 (as will be described below in detail in the description of Figure 8). Then for transmitting 415 a atom is assigned 420 to each transmitter. Intuitively the atom can be thought of as a value at each of q-ύme steps. The transmitter then encodes 425 a message by modulation onto the atom (for example for amplitude modulation a vector is created by multiplying the value of the atom at each time by the value of the message) [similar to the example in the embodiment of Figure I₅ where the message of a first transmitter is a_\ and the message of a second transmitter is a-i and the first transmitter encodes the message a._\ onto the atom δ(4) giving a signal which is a vector φ having values φ_/=α₁δ(4-/) and the second transmitter encodes the message O₂ onto another atom q^'ι/2cos(2π3t/q) giving a second vector φ where <p_j=a₂q^~ll2cos(2n3j/q)]. Then the resulting signal is sent 430 (for example by amplitude modulation where the digital code is made into an analogue radio wave having an amplitude corresponding to value of the encoded signal at the times corresponding to each element of the vector).

Receiving 435 the resulting a radio signal includes the steps of first generating the set of atoms. Then the composite radio wave resulting from the addition of the signals of the first and second transmitters is digitized 440 (in the case of amplitude modulation a vector of numbers are assigned each number corresponding to an amplitude of the received wave at a time). Then minimization is used to find 445 a sparse representation in terms of the atoms of the dictionary. By the theorems above, if the dictionary is N-sparse for N>2 then it is clear that the sparsest representation will have zero for all of the atoms and a._\ for the atom assigned to the first transmitter and OC₂ for the atom assigned to the second transmitter. The two messages corresponding to the coefficients Ot₁ and α₂ are then extracted 450.

Prior art CDMA used atoms that are pseudo-random codes. The orthagonality of these codes is not guaranteed, but if the length of the code is much longer than the number of transmitters, it is very unlikely that there will be a large cross correlation between codes. Thus when finding the value transmitted by a particular transmitter, the signals of others transmitters will interfere in a random way (some interfering more some less). Thus, the specificity of reception can be described by an ambiguity function. An example of an ambiguity function for CDMA using pseudo random codes is show in Figure 5. In CDMA the ambiguity function can be interpreted as the strength of reception a signal (shown at the origin) filtered by the received for a particular atom in a background of noise that are signals transmitted by modulating onto other atoms (illustrated as peaks not at the origin). It is seen that some the interfering peaks of the signals of other atoms are large while other interfering peaks are small. The largest interfering peak limits the reception of the signal on a noisy channel.

The ambiguity function of the Weil dictionary is show in Figure 6. It is seen that interference of all other atoms is consistently small. This allows better reception in the presence of a large number of transmitters. Furthermore, the Weil dictionary contains more differentiable atoms for a given signal length q than a pseudo random dictionary.

Attention is called to Figure 7, which is a flow chart illustrating an embodiment of a method of interpreting a radar signal. First there must be provided 710 a group of signals that can be detected and differentiated and optimized unambiguously in the time/frequency domain. A few of different signals are sent 735 out at different times and conditions of broadcast (or different directions). The echo of the compound signal is received 740 and digitized 750. Because there may be more than one object at various differences it is understood that the returning echo will be very complex with multiple peaks in the time/frequency plane as signals reflected from one object will return faster than signals reflected from another object. Therefore, it is necessary to detect the same signal with more than one phase and time shift. Thus the ideal ambiguity function is the thumbtack pattern of Figure 6 supplied by the Weil dictionary with weak cross and auto correlation allowing independent discrimination of signal form, phase shift and time shift. To find the correct peaks is exactly the same optimization 760 as described above for CDMA. From the time shift of each peak the operator knows the relative speed of the object and from the frequency modulation the operator knows the distance to the object and by changing wave form (i.e. using different atoms) as the signal sweeps over time and angle, the operator can determine the direction to the object and changes in its relative location and velocity.

Attention is called to Figure 8, which is a flow chart illustrating a method of generating a set of atoms spanning a signal space using Weil representation. The existence of a Weil representation of a Hubert space is known and was first described by Weil [Weil A., Sur certains groupes d'operateurs unitaires. Acta Math. I l l (1964) 143-211] and is known to those skilled in the art of theoretical mathematics. Nevertheless, the Abelian subgroups of the Weil representation described herein have never previously been publicly enumerated. Furthermore, the properties of the eigenvectors of the Abelian subgroups of the Weil representation have never been described and no one has ever suggested practical application of this theoretical construct. Unlike the Heisenberg system described above, the Weil representation has no continuous form and has never been applied in any way or form to radar, communication or sparsity.

The Weil representation allows representation of any finite Hubert space H(F₉") in terms of any appropriate symplectic group Sp(2n, F₉). In the following example for simplicity we illustrate the producing a Weil dictionary for a the one dimensional case («=1) the Weil represention is a map from SL(2, F₉) to the Hubert space H(F_q). Representation of a higher dimensional Hubert space may be by linearization and or by using a higher order symplectic representation. The treatment of higher dimensional Hubert spaces is therefore analogous to the treatment of a linear space described below and will be understood by those skilled from the description herein.

The first step of the method is to generate 810 a Heisenberg group. The group is a set of elements (τ, ω ,z) e F₉ x F₉ x F₉ with the multiplication rule

(T₁, COχ ,Zi)(T₂, CO₂ ,Z₂)= (Ti+Ti CD\+(JOi ,Z!+Z₂+(Ti CO₂- T₂Gh)IT).

The representation is given in terms of the time and frequency shift operators on the finite signal Hubert space. The time shift operator action is L(τ)S(f) = S(t + T) t; T e F₉. the frequency shift operator action is M(ω)S(t) = exp(2πiωt/q)S(f) t;ω e F₉.

The Heisenberg representation is denoted by π and given by τt(τ, ω ,z)=exp((πiωτ+2z)/q)M(ω)L(τ) and should be understood also as a qxq matrix.

The Heisenberg representation is irreducible and these operators span the algebra of all linear operators on that finite dimensional Hubert space. This means that for any operator /Ae [Z(H(F₉)) we can write A = ^T f_A (τ,ω,z)π(τ,co,z) with the function

T,ύ),z

/_A(T, ω ,z) over the Heisenberg group which depends on the operator A. We use this property to build the Weil representation and then the Weil dictionary.

The Weil representation a homomorphism of the group of 2x2 matrices whose elements belong to the finite field F₉ symbolized as SL(2,F_q) into the unitary operator on the Hubert space CZ(H(F₉)). Thus for 2x2 matrix geSL(2,F_q) the Weil representation is denoted by p(g)e [Z(H(F₉)). As stated above, since the operators of the Heisenberg representation span the Hubert space, we can write the Weil representation as p(g)= ∑£_g(τ,fi>,z)r(r,<ø,z). r.ffl.z

To enumerate the Weil representation we need a set of matrices g spanning SL(2,F_q). We will generate this set in two parts a set of q/2 matrices that we label gi(ό) and a set of q²/2 matrices that we label g_\\(b,c) where b,ceF_q.

First we initiate 815 a set of indices. The indices a and z are arbitrary and in the example of Figure 8 they are initiated to the value 2. The indices b and c will denote various sub-groups and are initiated to zero. Given a group, which as stated previously is a set of objects with a multiplication rule under which the set is closed, contains a neutral element and an inverse for any element in the set. A subgroup is a subset of the original set with the same multiplication rule that forms a group i.e. is closed, contains a neutral element and an inverse for any element in the subset.

As stated previously, we build dictionary by finding a common set of eigenvectors of a collection of commutative subgroups a.k.a. Abelian subgroups of the symplectic group. For the case of one dimensional signals, the symplectic space is SL(2,F_g). Various embodiments (collections) are possible. We describe here one such collections, other embodiments (collections) are possible based on the methodology outlined herein and are included.

The set of all diagonal matrices T in SL(2,F_g) with the usual matrix multiplication is a commutative subgroup. We denote this subgroup by

Using the Weil representation each 2 by 2 matrix in this subgroup T is assigned to a corresponding q by q unitary matrix. The representation preserves the group structure and therefore all these q by q matrices commute. As a consequence they share the same eigenvectors. These eigenvectors span the Hubert space. The algorithm takes an element of geT that generates the group T by powers, i.e. {T=g"\n~0,..., q-2}, and find the eigenvectors of p(T)={ p(g)\g an element in T} (since the eigenvectors are shared it is enough to find the eigenvectors of one member of T. Standard procedures for finding eigenvectors are available for example in the signals and linear algebra toolboxes of MATLAB® and many other commercially available mathematical packages). There are q eigenvectors of the q by q matrix. Thus, the subgroup T contributes q vectors to the dictionary. To create a large number of Abelian subgroups we now multiply a matrix T in front and behind by an arbitrary 2 by 2 matrix and its inverse. Clearly

is an Abelian subgroup for any g≡SL(2,F_q). We consider the collection of all Abelian subgroups of this type. The collection of eigenvectors from each subgroup is the proposed dictionary. Note that there is a large redundancy in this description since different group elements g may produce the same subgroup.

In order to find all such subgroups with less redundancies we parameterize the 51(2) group by the Bruhat decomposition. This decomposition asserts that any element g≡SL(2,F_q) can be written either as (a O Yl b)

with a, be F_q or as

Wύh a,b,c≡F_q.

Thus after initializing 815 a first part of the Bruhat decomposition g[ is specified.

Clearly the subgroup is not sensitive to the value of a and thus fixing α=2 and running over all b,ceF_q provides all subgroups. The number of such subgroups is q(q+l)/2. For each subgroup there are q eigenvectors each of which is an atom in the dictionary giving a total of q (q+Y)l2 atoms.

Once a 2 by 2 matrix gj representation has been specified 820 it is necessary to compute 825 the coefficients K^τ, ω ,z) for a member of the subgroup represented by gi this is done as follows.

where ψ(x)=exp(2πi x/q), v is a column vector such that v'=(z; ω), σ is the Legendre character [σ(α)=l if α=y² for some yeF_q and σ(α)=-l if a≠y² for any yeF_q], κ_g=(g+ I)(jg-I)^Λ is a 2 by 2 matrix that acts on two-dimensional vectors where / is the 2 by 2 identity matrix and

The eigenvectors of the q by q matrix ΣK_g{τ, ω ,z)π(τ, ω ,z) are then computed (standard software is available for computing the eigenvectors of a matrix [e.g. MATLAB® signals and linear algebra packages]. Such software is well known in the art and allows simple computation of these vectors once the matrix ∑K_g(τ, <y ,z)π(r, ω ,z) is known). The q eigenvectors for the subgroup represented by g^b-Qi) are then stored 830 on a storage device 801.

Once the eigenvectors associated with gi(b=0) have been stored 830, a second subset for

A new set of coefficients K_g are then computed 840 (by the same formula as above but using the new 2 by 2 matrix g_/f) for gii and the eigenvectors of the resulting q by q matrix ∑K_g(τ, ω ,z)π(τ, ω ,z) for gii(b=0,c=0) are computed 845 and stored 850 in a memory 801.

Once the eigenvectors associated with

have been stored 850, the index c is incremented 855, and if 860 the index c<q then a new 2 by 2 matrix

representing a new subgroup is specified 835 and if 860 c<q then a new set of coefficient K_g are then computed 840 for g_tI and the eigenvectors of the resulting q by q matrix K_g(τ, ω ,z)π(τ, ω ,z) for g_//(Z»=0,c=l) are computed 845 and stored 850 in a memory 801.

Thus the algorithm continues incrementing c until c=q. Thus for b=0 there was one subset associated with gj plus q subsets associated with gn for a total of q+l subsets associated with 6=0. If 860 c=q then all the atoms for 6=0 have been found. Therefore b is incremented and c is reinitialized to zero 865 and a new matrix gj is specified 820 and the loop continues for q values of b until b=q 870 at which point the loop ends 875 so that in the end there are q(q+l) subgroups each having q eigenvectors giving a total of q²(q+l) eigenvectors.

A dictionary of atoms Do which are the eigenvectors constructed by taking the eigenvectors of a representation of a finite symplectic group (a Weil representation) (for example in the example of Figure 8) is called the oscillator system. These signals constitute, in an appropriate formal sense, a finite analogue for the eigenfunctions of the harmonic oscillator in the real setting and, in accordance, they share many of the nice properties of the latter class. In particular, the dictionary Do satisfies the following properties

1) weak auto-correlation (ambiguity function) under time translation and frequency modulation. For every 5,2Do we have

The autocorrelation

(τ,ω)=0 and the autocorrelation is less then 2q^'m if either τ or ω is not 0.

2) weak cross-correlation (cross-ambiguity function) for all atoms and also under time translation and frequency modulation. For every Si≠S₂2Do we have the cross correlation

is less then or equal to Aq^{'1 2} for every τ and ωlF_p.

3) Small supremum. For every atom S2Do we have

4) Fourier invariance. For every atom 5"2Do the Fourier transform of S is also in Do The oscillator dictionary Do can be extended to a much larger dictionary DE, consisting of the order of q⁵ atoms if one is willing to compromise Properties 1 and 2 for a weaker condition. The extended dictionary consists of all atoms of the form MwLτS¹ for τ and ω eF_p and SeDo. It is not hard to show that the number of atoms in DE is q² times the number of atoms in Do. As a consequence of properties 1 and 2, for every Sι≠Si2De we have the cross correlation jhS¹ _/; S₂ij is less then or equal to 4q^'ιn .

All publications, patents and patent applications mentioned in this specification are herein incorporated in their entirety by reference into the specification, to the same extent as if each individual publication, patent or patent application was specifically and individually indicated to be incorporated herein by reference, hi addition, citation or identification of any reference in this application shall not be construed as an admission that such reference is available as prior art to the present invention.

In sum, although various embodiments and preferred versions thereof have been described in considerable detail, other versions are possible. Therefore, the spirit and scope of the appended claims should not be limited to the description of the preferred versions contained herein.

Claims

WHAT IS CLAIMED IS:

1. A dictionary at least partially spanning a set of discrete ^-length signals comprising: a) a representation of a commutative subgroup of a finite symplectic group, and b) a plurality of atoms wherein each atom of said plurality of atoms is an eigenvector of said representation.

2. The dictionary of claim 1, wherein said symplectic group is a n-dimensional matrix Sp(2n,F_q).

3. The dictionary of claim 1, wherein said plurality of atoms includes at least q (q + 1) +1 atoms.

4. The dictionary of claim 1, wherein a verifiable property of said plurality of atoms includes at least one property selected from the group consisting of a normalized peak-to-average power ratio of less the inverse of the square root of q (PMPR < q^' ^l/2), an autocorrelation under frequency modulation and time translation of less than 2

≤ 2(q + ]Xq - l)^~V ^)/2VS e D₀,ω ≠ 0 ), and a cross correlation of less tha ≤ A{_{q + &} D₀;ω,τ e F_q;i ≠ j ).

5. The dictionary of claim 4, wherein said at least one property is invariant under at least one operation selected from the group consisting of a Fourier transform, a quadratic modulation and a homothety.

6. The dictionary of claim 1, further comprising c) a minimization procedure for extracting a sparse representation of at least one of said signals in terms of at least one atom from said plurality of atoms.

7. The dictionary of claim 1, wherein said representation is a Weil representation.

8. The dictionary of claim 1, wherein said dictionary is applied to at least one task selected from the group consisting of interpreting a radar signal, denoising at least one of the signals, compressing data, finding a sparse representation, deblurring at least one of the signals, finding a sparse representation of at least one of the signals, encoding a symbol for communication, encoding at least one symbol for CDMA or OFDM communication, classifying a data set, generating an error correcting code and generating a random number.

9. A method of producing a dictionary at least partially spanning a set of discrete q- length signals comprising: a) defining a representation of a commutative subgroup of a finite symplectic group, and b) specifying a plurality of atoms wherein each of said plurality of atoms is an eigenvector of said representation.

10. The method of claim 9, wherein said symplectic group is Sp(2n,F_q).

11. The method of claim 9, wherein said plurality of atoms includes at least q(q+ 1) +1 atoms.

12. The method of claim 9, wherein the set of verifiable properties of said plurality of atoms includes at least one property selected from the group consisting of a normalized peak-to-average power ratio of less the inverse of the square root of q (PMPR < q^'m), an autocorrelation under frequency modulation and time translation of less than 2q ^m(q+ l)/fø-l) (|(S,Z_rM_ωS)| <2(₉ + lX?-l)^~V^/2VSe A_>^ ≠ 0)> and a cross correlation of less than 4(q+l)(q-\)^'lq^{~l 2} & D_ϋ-ω,τe F_q-J≠ j).

13. The method of claim 9, wherein said at least one property is invariant under at least one operation selected from the group consisting of a Fourier transform, a quadratic modulation and a homothety.

14. The method of claim 9, further comprising c) extracting a sparse representation of at least one of said signals in terms of at least one of said plurality of atoms.

15. The method of claim 9, wherein said representing is via a Weil representation.

16. The method of claim 9, further comprising c) The dictionary of claim 1 , wherein said dictionary is applied to at least one task selected from the group consisting of interpreting a radar signal, denoising at least one of the signals, compressing data, finding a sparse representation, deblurring at least one of the signals, finding a sparse representation of at least one of the signals, encoding a symbol for communication, encoding at least one symbol for CDMA or OFDM communication, classifying a data set, generating an error correcting code and generating a random number.

17. A method to interpret a radar signal comprising: a) providing a plurality of atoms wherein said atoms at least partially span a set of signals and each of said plurality of atoms is an eigenvector of a representation of a commutative subgroup of a finite symplectic group; b) determining a time shift of an echo of at least one of said signals.

18. The method of claim 17, further comprising: c) resolving a frequency modulation of said echo.

19. A method to acquire a sparse representation of a signal comprising: a) providing a plurality of atoms wherein said atoms at least partially span the signal and each of said plurality of atoms is an eigenvector of a representation of a commutative subgroup of a finite symplectic group; b) determining a sparse representation of the signal in terms of said atoms.

20. A method of communication using a set of signals comprising: a) providing a plurality of atoms wherein said atoms at least partially span the signals and each of said plurality of atoms is an eigenvector of a representation of a commutative subgroup of a finite symplectic group; b) encoding at least one of said signals using at least one atom from said plurality of atoms.