Currrent Research Projects

What is sparse signal processing?

Why is this research relevant to Ireland and to the world?

Sparse Signals

DUET and Desprit:
TM, CF, AM, NH, JH, RdeF, SR
Continuing research into the DUET blind source separation algorithm and its extensions.

NMF and applications
RdF, POG, KD, SR
Extensions of Non-negative Matrix Factorisation to a range of applications including financial data analysis, audio analysis and automatic ASCII art conversion.

The Darius Project:
CF, AM, SR
Using multi-channel heart sound recordings to localize and segment the phonocardiogram into its constituent components for automatic diagnosis of cardiac abnormalities.

Localization
AM, SR
Localizing sources using time delay/attenuation information

Sparse Measures
NH, SR
Comparison of Sparse Measures

Channels

Channel Models
NT, KD, SR
Wideband time-varying channel models

BLT Sandwich
NT, KD, SR
Investigation of the set of functions that are invariant under the repeated application truncation operations in frequency (B), scale (L) and time (T).

Costas

Enumeration and Database
KD, KT, JD, SR
Brute force enumerations of Costas arrays and the creation of a database with all enumeration results

Generalization
KD, KT, SR
Generalization of the Costas property to more complex structures (higher dimensions, continuum, larger sets of points)

Matlab Toolbox
KD, KT, SR
Furthering the enumeration and understanding of Costas arrays and their uses.

Correlations
KD, KT, SR
Cross-correlation of families of Costas arrays and determination of families with low cross-correlation

What is sparse signal processing?
A sparse signal has a large portion of its energy contained in a small number of coefficients. One obvious reason why we desire sparse representations of signals is because the more sparsely we can represent a signal, the more efficiently we can compress the signal. However, sparse representations allow us to do much more than just compression. For example, sparse representations allow us to violate the Nyquist sampling theorem without loss of fidelity. Sparse representations allow us to solve systems of equations with more unknowns than constraints, which in turn leads to solutions to previously insolvable blind source separation problems (ie. the cocktail party problem).
Sparse signal processing is the application of the mathematics of sparse representations to problems in signal processing including speech processing, biomedical signal processing, financial time-series analysis, and communications.

Why is this research relevant to Ireland and to the world?
7 in 10 echocardiograms are unnecessary and cost medical insurance companies to waste billions of Euro annually. More importantly, the tragedy of Sudden Cardiac Death in the Young, which is the loss of a young life due to undiagnosed cardiac problems, is an avoidable one. There are approximately 10,000 cardiac deaths per year in Ireland.
64% of all these deaths are out of hospital sudden cardiac arrests. This corresponds to approximately 20% of all deaths in Ireland. Many of the deaths are preventable if individuals at high risk could be identified at low cost. The SSPG Team has established a collaboration with cardiologists in St. Vincent's University Hospital and the U.S.-based Zargis Medical Corporation and are creating a cost-effective acoustic imaging apparatus which creates an image of the beating heart created from sound waves, revealing defects and anomalies non-invasively. The eventual product will save lives and money.

Access to voice, video and high-speed data when mobile is one of the emerging challenges in digital communications. In order to get the data, the communications system must understand the link between the transmitter and the receiver. When either (or both) are moving, this challenge becomes significantly more difficult. Members of the SSPG Team have created novel mathematical descriptions of these changing conditions which will result in more reliable communication (and fewer dropped calls!).

Can you arrange 8 Queens on a chess board so that none of them attack each other? It's not just a game, members of the SSPG Team are studying this and related problems using the mathematics of prime numbers to develop communication systems which will allow for more efficient use of the wireless spectrum resulting in better quality mobile phone conversations.

back to top

DUET and Desprit:

SSPG Team – C. Fearon, A. Moni, N. Hurley, R. De Fréin, S. Rickard, T. Melia

Collaborators –

Radu Balan, University of Maryland

Professor Barak Pearlmutter, Hamilton Institute, National University of Ireland, Maynooth, Ireland.

Ozgur Yilmaz, University of British Columbia

C. Took, Cardiff University

S. Sanei, Cardiff University

J. Chambers, Cardiff University

S. Dunne, Cardiff University

Naomi Harte, TCD

Background and Motivation

The goal in Blind Source Separation (BSS) is to recover the original sources given only mixtures of the sources. Our research in blind source separation has focused on the case when there are more sources than mixtures. Such mixtures are called underdetermined or non-square and demixing by inverting the mixing matrix is not possible. One strategy for attacking this problem has been to project the mixtures into a representation where the sources have sparse represenations, and then make the assumption that in the sparse representaion large energy coeefficients are likely to correspond to only one (or a small
number) of active sources. Demixing is then possible via partitioning. One method which uses this approach is the DUET blind source separation algorithm. The algorithm uses a two-dimensional histogram constructed from the ratio of the time-frequency representations of the two channels of a stereo mixture which is shown to have one peak for each source with peak location corresponding to the relative attenuation and delay mixing parameters. The histogram is used to create time-frequency masks which partition one of the mixtures into the original sources.
The DUET Blind Source Separation algorithm is capable of demixing N > 2 speech signals using only M = 2 anechoic mixtures of the signals.

Goals

Our current work seeks to extend DUET to

the multichannel case when there are many mixtures available (M>1),

situations where the source signals may overlap significantly in the time-frequency domain,

echoic environments where an anechoic mixing model is implausible.

Progress to Date

Published summary of DUET (and MATLAB code) with extension to non-closly spaced microphones [1].

Developed novel extension of DUET to multiple channels and echoic environments (for linear or paired arrays of microphones) [2]

Developed MATLAB software toolbox implementaion of DUET [3]

Implemented DUET in low-cost low-power hardware (proof-of-concept) [4]

Selected Outputs

[1] Scott Rickard. The DUET Blind Source Separation Algorithm, pages 217-237, book chapter in Blind Speech Separation, Eds. Shoji Makino, Te-Won Lee, Hiroshi Sawada, Springer, 2007

[2] Tom Melia, Scott Rickard. Underdetermined Blind Source Separation in Echoic Environments Using DESPRIT. EURASIP Journal on Advances in Signal Processing, Article ID 86484, 19 pages, 2007.

[3] Scott Rickard and Conor Fearon. DUET MATLAB Software Implementation. 2006.

[4] Naomi Harte, Niall Hurley, Conor Fearon, and Scott Rickard. Towards a Hardware Realization of Time-Frequency Source Separation of Speech. European Conference on Circuit Theory and Design, 1: I/71–I/74 vol. 1, August 2005.

link to full list of Publications in this area

Sponsors:
Science Foundation Ireland
Enterprise Ireland
IRCSET

back to project list

NMF and applications:

SSPG Team –R. de Fréin, P. O'Grady, S. Rickard, K. Drakakis

Collaborators –

Dr. Andrezj Cichocki, Brain Science Institute, The Laboratory for Advanced Brain
Signal Processing, (ABSP), Japan.

Professor Barak Pearlmutter, Hamilton Institute, National University of Ireland, Maynooth, Ireland.

Frank Duignan, Dublin Institute of Technology, Dublin, Ireland.

Background and Motivation
Non-negative matrix factorization learns low rank representations of data ensembles of the
form $Y = DC$, where $Y \in \Re^{M×N \ge 0}, $D \in \Re^{ M×R \ge 0}$ and $C \in \Re^{R×N \ge }0 . It is an iterative alternating algorithm, meaning that it minimizes an objective function, for example, the Squared Euclidean Distance (SED), by fixing one factor and minimizing the other in an alternating fashion.

This project is an investigation of two topics in the field of signal processing. Firstly, the development of new algorithms for learning user specific dictionaries/frames, exploiting sparse representations of speech signals with applications in source separation and speech recognition. Secondly, developing new algorithms and approaches for analysis of financial data. This project deals with adding sparsity constraints to the NMF objective to learn intuitive and detailed features rich in meaning even to a newcomer to the field. In doing this we have collaborated with the leaders in the field to advance the state of the art.

Progress to Date

Waiting for notification of acceptance of a paper sent to Irish Signals and Systems Conference 2008 (ISSC 08)

Submission to the International Journal of Mathematical Finance of fleshed out and extended results presented in [2].

Goals

The first goal is to investigate the underlying mathematics of Non negative matrix factorization.
A second goal is to broaden the range of problems to which NMF is applicable.
Developing new techniques for performing NMF decompositions suited to the underlying characteristics of the data ensemble.

Selected Outputs

K. Drakakis, S. Rickard, R. de Frein, and A. Cichocki. Analysis of financial data using non-negative matrix factorization. International Journal of Mathematical Sciences, 6(2), 2007.

R. de Frein, K. Drakakis, and S. Rickard. Portfolio diversification using subspace factorization. Proceedings of the 42th Annual Conference on Information Sciences and Systems, Princeton, NJ, USA, June 2008.

NMFLAB, Algorithms for Non-Negative Matrix Factorization, http://www.bsp.brain.riken.jp/index.php

S. Rickard and Andrzej Cichocki, When is non-negative matrix decomposition unique?, Proceedings of the 42th Annual Conference on Information Sciences and Systems, Princeton, NJ, USA (2008).

link to full list of Publications in this area

Key Relevant Work by Others

D. D. Lee and H. S. Seung. Learning the parts of objects by non-negative matrix factorization. Nature, 401(6755):788791, October 1999.
Abstract Is perception of the whole based on perception of its parts? There is psychological1 and physiological2,3 evidence for parts-based epresentations in the brain, and certain computational theories of object recognition rely on such representations4,5. But little is known about how brains or computers might learn the parts of objects. Here we demonstrate an algorithm for non-negative matrix factorization that is able to learn parts of faces and semantic features of text. This is in contrast to other methods, such as principal components analysis and vector quantization, that learn holistic, not parts-based, representations.Non-negative matrix factorization is distinguished from the other methods by its use of non-negativity constraints. These constraints lead to a parts-based representation because they allow only additive, not subtractive, combinations. When non-negative matrix factorization is implemented as a neural network, parts-based representations emerge by virtue of two properties: the firing rates of neurons are never negative and synaptic strengths do not change sign.

D. Donoho and V. Stodden. When does non-negative matrix factorization give a correct decomposition into parts. Advances in Neural Information Processing Systems, 16, 2003.
Abstract We interpret non-negative matrix factorization geometrically, as the problem of finding a simplicial cone which contains a cloud of data points and which is contained in the positive orthant. We show that under certain conditions, basically requiring that some of the data are spread across the faces of the positive orthant, there is a unique such simplicial cone. We give examples of synthetic image articulation databases which obey these conditions; these require separated support and factorial sampling. For such databases there is a generative model in terms of parts and NMF correctly identifies the parts. We show that our theoretical results are predictive of
the performance of published NMF code, by running the published algorithms on one of our synthetic image articulation databases.

Sponsors:
Science Foundation Ireland
IRCSET

back to project list

The Darius Project:

SSPG Team – C. Fearon, A. Moni, S. Rickard

Collaborators –

Dr. Martin Quinn (St. Vincents University Hospital)

Raymond Watrous (Zargis Medical Corp.)

Background and Motivation
Auscultation of the heart has long been a powerful yet cost-effective procedure that provides physicians with information on the timing, duration, pitch, location and intensity of normal heart sounds. However, the advancement of technology has caused auscultation to become a neglected art and has brought into question the ability of physicians to accurately detect abnormal cardiac findings through physical examination. Hence, a diagnostic aid that would assist the physician in discerning heart sounds would both increase the accurate detection of cardiac abnormalities and reduce the number of unnecessary referrals for more expensive and sometimes invasive procedures. This research involves developing a method which uses multi-channel heart sound recordings to localize heart sound energy and separate the phonocardiogram into its constituent components.

Progress to Date

The main focus of our research to date has been the detection and localisation of the turbulent sounds produced by coronary artery stenosis. The current gold standard for diagnosis of coronary artery disease (CAD) is the coronary angiogram, an invasive procedure with associated risk. The development of a non-invasive method of diagnosis would both reduce the risk associated with diagnosis and provide a user-friendly system for screening the general public for CAD.

Much of our research efforts have been dedicated to development of a suitable data acquisition system. After several iterations, we have finally built a portable prototype system for use in a clinical setting with which we will begin collecting a large data set of patient with CAD. The critical factor in the detection of these low-amplitude turbulent sounds is sensor quality. To this end, we have extensively investigated the usefulness of many different types of sensor including electronic stethoscopes, piezoelectric pressure transducers and adhesive PVDF sensors.

We have also developed an algorithm for multi-sensor blind source separation which we intend to use for localisation of the turbulent sounds. Further algorithm development will take place when a complete data set has been collected.

We have also developed a suitable way to model coronary artery stenoses in a human thorax, consisting of stenosed latex tubes embedded in a mould of ballistics gel designed to mimic the density and acoustic properties of the human thorax. Preliminary experiments on this model have proved the concept of coronary stenosis detection.

We are continuing to collaborate with Zargis Medical Corp. (a medical devices company from Princeton, NJ specialising in the detection of heart sounds for diagnostic purposes) on the topic of system and algorithm development. Zargis has a developed an FDA-approved murmur detection device which is currently in production. We also collaborating with Dr. Martin Quinn, a consultant cardiologist at St. Vincent’s University Hospital and we have ethical approval for the recording of patients with coronary artery disease pre- and post-angioplasty which will commence this summer.

Goals

Record a database of 30 patients with single vessel disease and no other diastolic murmurs pre- and post-angioplasty and analyse.

Record a database of 30 patients with no disease (age, sex and MI adjusted to above)

Record database of patients with multiple occlusions, with and without other diastolic murmurs.

Make recordings from ballistics gel model varying parameters such as degree, length, and asymmetry of stenosis, distance of stenosis from sensors (i.e. depth in ballistics gel/thorax), number of simultaneous stenoses. These experiments will give us insight into how these parameters affect amplitude, frequency and location of turbulent sound and allow me to evaluate the limits of the algorithm.

Further algorithm development and blind clinical trial

Selected Outputs

C. Fearon and S. Rickard, "Multichannel Phonocardiogram Source Separation and Localization," 3rd European Medical and Biological Engineering Conference, Prague, Czech Republic, November 2005.

T. Melia, C. Fearon and S. Rickard, "Extending the DUET Blind Source Separation Technique,"
Signal Processing with Adaptive Sparse Structured Representations, Rennes, France,November 2005.

S. Rickard, T. Melia and C. Fearon, "DESPRIT - Histogram Based Blind Source Separation of More Sources than Sensors using Subspace Methods," IEEE Workshop on Applications of Signal Processing to Audio and Acoustics, New Paltz, New York, October 2005.

T. Melia, S. Rickard, and C. Fearon, "Histogram Based Blind Source Separation of More Sources than Sensors using a DUET-ESPRIT Technique," 13th European Signal Processing Conference, Antalya, Turkey, September 2005.

C. Fearon and S. Rickard, "Multichannel Phonocardiogram Source Separation," IEEE EMBSS UKRI Postgraduate Conference on Biomedical Engineering and Medical Physics, University of Reading, UK, July 2005.

link to full list of Publications in this area

Key Relevant Work by Others

Akay, M.   Semmlow, J.L.   Welkowitz, W.   Bauer, M.D.   Kostis, J.B, “Detection of coronary occlusions using autoregressive modeling ofdiastolic heart sounds”, IEEE Transactions on Biomedical Engineering, vol.37, no.4, pp. 366-373, April 1990
Abstract:
Recordings of diastolic heart sound segments were modeled by autoregressive (AR) methods including the adaptive recursive least-squares lattice (RLSL) and the gradient lattice predictor (GAL). Application of the Akaike criterion demonstrated that between 5 and 15 AR coefficients are required to describe a diastolic segment completely. The reflection coefficients, prediction coefficients, zeros of the polynomial of the inverse filter, and AR spectrum were determined over a number (N=20-30) of diastolic segments. Preliminary results indicate that the averaged AR spectrum and the zeros of the inverse filter polynomial can be used to distinguish between normal patients and those with coronary artery disease

Akay, M.   Semmlow, J.L.   Welkowitz, W.   Bauer, M.D.   Kostis, J.B.  , “Noninvasive detection of coronary stenoses before and after angioplasty using eigenvector methods”, IEEE Transactions on Biomedical Engineering, vol.37, no.11, pp. 1095-1104, November 1990.
Abstract:
Previous studies suggest that partially occluded coronary arteries may generate sounds due to turbulent blood flow. To support these findings, the frequency spectra of diastolic heart sounds are compared before and after angioplastic surgery. Since the low-level sounds associated with partially occluded coronary arteries are contaminated with considerable background noise, traditional FFT analysis may not produce accurate frequency spectra. In a previous study using the same data, no significant differences were found in the diastolic heart sounds before and after angioplastic surgery. In this study, three eigenvector methods (Pisarenko, MUSIC, and Minimum-Norm) have been selected to generate the frequency spectra because of their higher resolution, particularly in the presence of noise. Although the Pisarenko method produced spurious zeros and could not be used, the other two methods produced spectra showing, in most cases, a marked decrease in high-frequency spectral components following angioplasty

Sponsors:
Science Foundation Ireland
IRCSET

back to project list

Localization

SSPG Team – A. Moni, S. Rickard

Collaborators –

Chris Bean (Geophysics Group, UCD)

John Leonard (Computer Science and Artificial Intelligence Laboratory, MIT)

Background and Motivation
The problem of localization is relevant in many fields including navigation, meteorology, geology, networking. Applications include positioning systems, video conferencing (steer camera to direction of acoustic wave),   locating epicenters of earthquakes, locating lightning sources and many other applications.

With a number of sensors scattered around a room, for every pair of sensors an equation of a sphere results when using attenuation estimates to the source of unknown location and the sensor locations. When using time delay estimates to unknown source location and known sensor locations, an equation of a hyperboloid results for every pair of sensors. With both time delay estimates and attenuation estimates, the range to each sensor from the unknown source location can be calculated. The problem of localization becomes one of intersecting these geometric shapes.

Goals

Find the best algorithm to locate a source with known sensor locations and time delay estimates and/or attenuation estimates
Have a real time 3D demo working to visualize the localization. A cube that represents a room with weights at each point depending on the probability of finding the source at the point.
Sensors are deployed around a room. They communicate with each other to find out their locations. Using this information, they can track a moving object in the room. To do this, the sensors should be able to find distances to each other (synchronized clocks or using two different waves and their difference in speed to calculate distance traveled)

Progress to Date

Existing localization algorithms including closed form techniques and iterative methods have been reviewed and compared with each other. A spatial histogram algorithm has been used to locate sources and compared with established closed form techniques and an iterative technique that is used for GPS and has shown superior results.

Collaborative series of talks on localization have been organized in CASL – there have been three talks so far.

3D visualization tool is under construction

Selected Outputs

“Maximum Likelihood Estimation in Sparse Systems and the PowerWeighted Histogram Estimation Tool", T. Melia, A. Moni, S. Rickard, IMA International Conference on Mathematics in Signal Processing, The Royal Agricultural College, Cirencester, December 2006.

“Comparison of Localization Algorithms using Attenuation estimates”, Aishwarya Moni, Scott Rickard – submitted to EUSIPCO 2008

“Comparison of Localization Algorithms using Time Delay of Arrival estimates”, Aishwarya Moni, Scott Rickard – Submitted to IMA 2008

link to full list of Publications in this area

Sponsors:
Science Foundation Ireland

back to project list

Sparse Measures

SSPG Team – N. Hurley, S. Rickard

Collaborators –

R. Balan (UMD)

P. Curran (UCD)

A. Cichocki (RIKEN)

M. Fallon (Cambridge)

J. Rosca (Siemens Corporate Research, Princeton, NJ, USA.)

Background and Motivation
Sparsity is a tricky thing to define. A sparse signal is a signal which has most of its energy in just a few coefficients. Measuring how sparse a signal is, however, is the subject of some debate. Should we count the number of zero coefficients? Should we calculate the percentage of low energy coefficients? Perhaps we should calculate the peakedness of the signal? In this project we ask what properties compare commonly-used measures of sparsity.

Many algorithms for blind source separation, compression, and sampling rely on sparsity. For example, one method of source separation is to transform the signal to a domain in which it is sparse (e.g. time-frequency or wavelet) where the separation can be performed by a partition of the transformed signal space due to the sparsity of representation.

There are many measures of sparsity, e.g. number of zero-valued coefficients, number of non-zero coefficients, number of coefficients above or below a threshold. Intuitively, a sparse representation is one in which a small number of coefficients contain a large proportion of the energy. This interpretation leads to further possible alternative measures. Indeed, there are dozens of measures of sparsity
proposed in the literature. Which of the sparse measures is the best? We suggest some desirable characteristics a measure of sparsity should have and use them to compare popular sparsity measures.

The following are six desirable attributes of a measure of sparsity. The first four, D1 through D4, were originally applied in a financial setting to measure the inequity of wealth distribution by Dalton (1920). The last two, P1 and P2, were proposed in by
Rickard et al (2004). Distribution of wealth can be used interchangeably with distribution of energy of coefficients and where convenient in this paper, we will keep the financial interpretation in the explanations. Inequity of distribution is the same as sparsity. An equitable distribution is one with all coefficients having the same amount of energy. This is the least sparse distribution.

D1 (Dalton's 1st Law) a.k.a. Robin Hood - Robin Hood decreases sparsity. Stealing from the rich and giving to the poor, decreases the inequity of wealth distribution (assuming we do not make the rich poor and the poor rich). This comes directly from the definition of a sparse distribution being one for which most of the energy is contained in only a few of the coefficients.

D2 (Dalton's modified 2nd Law (see Arnold (1986)) a.k.a. Scaling - Sparsity is scale invariant. Multiplying wealth by a constant factor does not alter the effective wealth distribution. This means that relative wealth is important, not absolute wealth. Making everyone ten times more wealthy does not affect the effective distribution of wealth. The rich are still just as rich and the poor are still just as poor.

D3 (Dalton's 3rd Law) a.k.a. Rising Tide - Adding a constant to each coefficient decreases sparsity. Give everyone a trillion dollars and the small differences in overall wealth are then negligible so everyone will have the same wealth. This is intuitive as by adding a constant energy to each coefficient reduces the relative difference of energy between large and small coefficients.

D4 (Dalton's 4th Law) a.k.a. Cloning - Sparsity is invariant under cloning. If there is a twin population with identical wealth distribution, the sparsity of wealth in one population is the same for the combination of the two.

P1 a.k.a Bill Gates - Bill Gates increases sparsity. As one individual becomes infinitely wealthy, the wealth distribution becomes as sparse as possible.

P2 a.k.a. Babies - Babies increase sparsity. Adding individuals with zero wealth to a population increases the sparseness of the distribution of wealth.

These criteria give rise to the sparsest distribution being one with one individual owning all the wealth and the least sparse being one with everyone having equal wealth. These criteria can also be expressed mathematically which will appear in a publication currently being reviewed for EUSIPCO2008. Only one sparse measure satisfies all six criteria - The Gini Index.

Progress to Date

Appropriate behaviour for a sparse measure established: The Six Sparse Thoughts. (see above)

Sparsification of a signal using the Gini Index
One of the interesting properties of wavelets is that from a given mother wavelet, a new wavelet can be made via a 'lifting procedure' and thus modified to be more effective for some purpose, (e.g. efficient representation). Using such a system, we can search the space of wavelets and choose the 'best' lift with some optimization criterion or constraint in mind. As an application of our method, in this paper we determine the lifted wavelet basis that increases the sparsity of a signal's wavelet representation. Preliminary results indicate that Gini is a successful sparse measure for use with wavelets

Future Goals

Compare commonly-used measures of sparsity [1]
Demonstrate the effectiveness of choosing an appropriate measure of sparsity
Optimize a cost function through the sparsity measure
Demonstrate the the utility of the six sparse thoughts using real data

Selected Outputs

Niall Hurley, Scott Rickard, Comparing Measures Of Sparsity. Submitted to EUSIPCO 2008, Lausanne, Switzerland, August 2008.

Niall Hurley, Scott Rickard, Paul Curran, and Konstantinos Drakakis. Maximizing Sparsity of Wavelet Representations via Parameterized Lifting. Digital Signal Processing, 15th International Conference on, ():631–634, July 2007.

Niall Hurley, Scott Rickard, and Paul Curran. Parameterized Lifting for Sparse Signal Representations Using the Gini Index. In Signal Processing with Adaptative Sparse Structured Representations (SPARS05), Rennes, France, November 2005.

Scott Rickard. Sparse sources are separated sources. In Proceedings of the 16th Annual European Signal Processing Conference, Florence, Italy, 2006.

Scott Rickard and M. Fallon. The Gini Index of Speech. Conference on Information Sciences and Systems ,Princeton, NJ, March 2004.

link to full list of Publications in this area

Key Relevant Work by Others

J. Karvanen and A. Cichoki. Measuring Sparseness of Noisy Signals. In ICA03, 2003.
Abstract: In this paper sparseness measures are reviewed, extended and compared. Special attention is paid on measuring sparseness of noisy data. We review and extend several definitions and measures for sparseness, including the L_0, L_p and ... norms. A measure based on order statistics is also proposed. The concept of sparseness is extended to the case where a signal has a dominant value other than zero. The sparseness measures can be easily modified to correspond to this new definition. Eight different measures are compared in three examples. It turns out that different measures may give complete opposite results if the distribution does not have a unique mode at zero. As conclusion, we suggest that the kurtosis should be avoided as a sparseness measure and recommend tanh-functions for measuring noisy sparseness.

K. Kreutz-Delgado and B. D. Rao. Measures and Algorithms for Best Basis Selection. In ICASSP1998, Seattle, Washington, USA.
Abstract: A general framework based on majorization, Schur-concavity, and concavity is given that facilitates the analysis of algorithm performance and clarifies the relationships between existing proposed diversity measures useful for best basis selection. Admissible sparsity measures are given by the Schur-concave functions, which are the class of functions consistent with the partial ordering on vectors known as majorization. Concave functions form an important subclass of the Schur-concave functions which attain their minima at sparse solutions to the basis selection problem. Based on a particular functional factorization of the gradient, we give a general affine scaling optimization algorithm that converges to a sparse solution for measures chosen from within this subclass.

C. Gini. Measurement of inequality of incomes. Economic Journal, 31:124–126, 1921.
Abstract: n/a

B. C. Arnold. Majorization and the Lorenz Order: A Brief Introduction, Springer-Verlag, 1986.
Abstract: n/a

H. Dalton. The measurement of the inequity of incomes. Economic Journal, 30:348–361, 1920.
Abstract: n/a

M. O. Lorenz. Methods of Measuring Concentrations of Wealth. J. Amer. Stat. Assoc., 1905.
Abstract: n/a

Sponsors:
Science Foundation Ireland

back to project list

Channel Models and BLT Sandwich

SSPG Team – N. Tsakalozos, K. Drakakis, S. Rickard

Collaborators – A. Papandreou-Suppappola (Arizona State University), R. Balan (University of Maryland), H. Vincent Poor (Princeton University), S. Verdu (Princeton University)

Background and Motivation
"The world is a time-scale operator.’’ This statement is not entirely accurate. However, it is more valid than the standard assumption we were all taught which models the world as a time-delay operator. Indeed, the time-delays alone are sufficient to model the path effects for narrowband signals in a stationary multipath environment. But, wideband mobile environments cannot be modelled efficiently using time-delays alone and new models are needed. When we send a signal x from A to B, the received signal is a time-shifted and time-scaled version of the signal we transmit. The time-shifting arises from the distance between A and B and the time-rescaling is caused as the result of the relative motion of A and B (we are considering here a one path model with the relative motion of A and B having constant radial velocity). We can represent the physical system inefficiently by using many time-shifts operations, but the inherent purpose of a RAKE receiver model is to capture the many time-shifts caused by the multi-paths. The RAKE receiver is not the appropriate tool to use when scale shifts become significant. Thus the time-scale model is the appropriate tool to capture the wideband time-varying channel. It turns out, that, in some scenarios, time-frequency operators can be effective channel models and can be used to substitute time-scale operators, to a point. The work in this project studies the underpinning mathematics of time, time-frequency, time-scale, and frequency-scale (and time-frequency-scale?) operators with the goal being their exploitation in the area of communications (SONAR/RADAR settings). We are interested in determining which model we should use as a function of the time-bandwidth (or scale-width!) product of the signal as well as the relative speed of movement between the transmitter and the receiver.

Progress to Date

Developed models and interpretations from a communications point of view of the time, time-frequency, time-scale and frequency-scale characterizations of linear time-varying channels [1,2].

Measured the efficiency (sparsity) of the time-domain characterization, the time-frequency characterization and the time-scale characterization for the case of a linear time-varying one path physically-based deterministic channel model. We have considered the efficiency of three different representations (time-domain, time-frequency and time-scale) for a one-path linear time-varying deterministic channel following two approaches. The first approach was focused in measuring how well each of the discrete representations reconstructs the channel when a limited amount of coefficients is available [3]. The second approach consisted in quantifying for each of the above representations how well the input-output relationship was captured by the discrete coefficients for modulated Gabor pulse input signals [4].

Derivation of the input-output relationship of time-varying channels (the Doppler effect) from Newtonian mechanics, Maxwell’s equations and Minkowski diagrams. In [5] we derived from first principles both the Newtonian and the relativistic input-output relationships for transmitter and receiver moving directly towards or away from each other with constant speed. In order to establish the relations for the relativistic scenario we used the Minkowski diagram. We showed that in the case where the velocities are small, the non-relativistic model can be considered as a very good approximation of the relativistic one. In [6] we derived the relativistic model using the Maxwell’s equations and showed that the two ways (Minkowski’s diagram and relativistic electromagnetics) lead to the same result. The conclusion is that there is only one Doppler effect. We also observed that although the Doppler effect is a rescaling rather than a frequency translation, it can be approximated well by an additive frequency shift under the usual narrowband assumption for most practical purposes. We ended our study by highlighting a list of applications where the Doppler effect plays a vital role. After all the Doppler effect is not an abstract concept; in contrary myriads of applications (the most well known of them is the GPS) exploit this phenomenon.

Goals

Continue the study of the time, time-frequency, time-scale and frequency-scale representations of linear time-varying channels (and associated RAKE models) to determine the relationship between time-bandwidth product of the signal, relative speed of transmitter-receiver, and model efficiency (sparsity).
The BLT Sandwich: Investigation of the set of functions that are invariant under the repeated application truncation operations in frequency (B), scale (L) and time (T)

Selected Outputs

R. Balan, V. Poor, S. Rickard, S. Verdu, “Time-Frequency and Time-Scale Canonical Representations of Doubly Spread Channels”, Proceedings of the 12th European Signal Processing Conference, Vienna, Austria, pages 445-448, September 2004.

S. Rickard, R. Balan, V. Poor, S. Verdu, “Canonical Time-Frequency, Time-Scale, and Frequency-Scale Representations of Time-Varying Channels”, Journal on Communications in Information and Systems, vol.5, no.2, pp.197-226, November 2005.

S. Rickard, K.Drakakis and N. Tsakalozos, “On the efficiency of time-varying channel models”, Proceedings of the 40th Annual Conference on Information Sciences and Systems (CISS), Princeton, NJ, March 22-24 2006.

S. Rickard, K. Drakakis and N. Tsakalozos, “Time-varying channel model efficiency”, Proceedings of the 14th European Signal Processing Conference EUSIPCO 2006, Florence, Italy, September 4-8, 2006.

S. Rickard, K.Drakakis and N. Tsakalozos, “A comparison of the classic and relativistic Doppler effect in linear time-variant channel models”, Proceedings of the 7th International Conference on Mathematics in Signal Processing, The Royal Agricultural College, Cirencester, United Kingdom, December 18–20, 2006.

S. Rickard, K.Drakakis and N. Tsakalozos, “A comparison of the classic and relativistic Doppler effect in linear time-variant channel models”, submitted to IEEE Transactions on Wireless Communications.

link to full list of Publications in this area

Key relevant work by others:

L.G. Weiss, “Wavelets and Wideband Correlation Processing”, IEEE Signal Processing Magazine, vol.11, no.1, pp.13-32, January 1994
Abstract:
This tutorial presents the application of wavelet transforms to wideband correlation processing. One major difference between most applications of wavelets and the work presented is the choice of mother wavelet. It focuses on nonorthogonal, continuous mother wavelets, whereas most applications use the orthogonal mother wavelets that were advanced by Daubechies (1988). The continuous wavelet transform then provides an additional tool for studying and gaining insight into wideband correlation processing. In order to understand when wideband processing may be required, its counterpart, narrowband processing, is presented and its limitations are discussed. Identifying those applications requiring wideband processing and presenting techniques to implement the processing are two of the goals of this tutorial article. The underlying tool is the wavelet transform.

A. Sayeed and B. Aazhang, “Joint multipath-Doppler diversity in mobile wireless communications”, IEEE Transactions on Communications, vol.47, no.1, pp.123-132, January 1999.
Abstract:
We introduce a new approach for achieving diversity in spread-spectrum communications over fast-fading multipath channels. The RAKE receiver used in existing systems suffers from significant performance degradation due to the rapid channel variations encountered under fast fading. We show that the Doppler spread induced by temporal channel variations in fact provides another means for diversity that can be further exploited to combat fading. We develop the concept of Doppler diversity and propose a framework that exploits joint multipath-Doppler diversity in an optimal fashion. Performance analysis shows that even the relatively small Doppler spreads encountered in practice can be leveraged into significant diversity gains via our approach. The framework is applicable in several mobile wireless multiple access systems and can provide substantial performance improvement over existing systems.

A. Sayeed and B. Aazhang, “Time-selective signaling and reception for communication over multipath fading channels”, IEEE Transactions on Communications, vol.48, no.1, pp.83-94, January 2000.
Abstract:
The mobile wireless channel affords inherent diversity to combat the effects of fading. Existing code-division multiple-access systems, by virtue of spread-spectrum signaling and RAKE reception, exploit only part of the channel diversity via multipath combination. Moreover, their performance degrades under fast fading commonly encountered in mobile scenarios. In this paper, we develop new signaling and reception techniques that maximally exploit channel diversity via joint multipath-Doppler processing. Our approach is based on a canonical representation of the wireless channel, which leads to a time-frequency generalization of the RAKE receiver for diversity processing. Our signaling scheme facilitates joint multipath-Doppler diversity by spreading the symbol waveform beyond the intersymbol duration to make the channel time-selective. A variety of detection schemes are developed to account for the intersymbol interference (ISI) due to overlapping symbols. However, our results indicate that the effects of ISI are virtually negligible due to the excellent correlation properties of the pseudorandom codes. Performance analysis also shows that relatively small Doppler spreads can yield significant diversity gains. The inherently higher level of diversity achieved by time-selective signaling brings the fading channel closer to an additive white Gaussian noise channel, thereby facilitating the use of powerful existing coding techniques for Gaussian channels.

A.R. Margetts, P. Schniter and A. Swami, “Scale-lag diversity reception in mobile wideband channels”, Proceedings of the IEEE conference on Acoustics, Speech, and Signal Processing (ICASSP), vol.3, pp.321-324, March 2005.
Abstract:
We consider the effect of mobility on a wideband direct sequence spread spectrum (DSSS) communication system, and study a scale-lag Rake receiver capable of leveraging the diversity that results from mobility. A wideband signal has a large bandwidth-to-center frequency ratio, such that the typical narrowband Doppler spread assumptions do not apply to mobile channels. Instead, we assume a more general temporal scaling phenomenon, i.e., a dilation of the transmitted signal's time support. Such analysis applies, for example, to ultra-wideband (UWB) radio frequency channels and underwater wideband acoustic channels.

Y.Yiang, A. Papandreou-Suppappola, “Time-scale canonical model for wideband system characterization”, Proceedings of the IEEE conference on Acoustics, Speech, and Signal Processing (ICASSP), vol. 4, pp.281-284, March 2005.
Abstract:
In this paper, we propose a time-scale canonical model as a discrete characterization of wideband linear time-varying systems. This representation decomposes a system output into discrete time shifts and Doppler scalings on the input, weighted by a smoothed discrete version of the wideband spreading function. We base this formulation on the Mellin transform that is matched to scalings. We also demonstrate that our proposed model inherently affords a joint multipath-scale diversity in wideband communication channels. By properly designing the signaling and reception schemes using wavelet techniques, we can achieve this diversity over a dyadic time-scale framework.

Y.Yiang, A. Papandreou-Suppappola, “Discrete time-scale characterization of wideband time-varying systems”, IEEE Transactions on Signal Processing (and IEEE Transactions on Acoustics, Speech and Signal Processing), vol.54, no.4, pp.1364-1375, April 2006.
Abstract:
Wideband time-varying systems can be found in many applications, including underwater acoustics and ultra-wideband technologies. The time variation due to Doppler scaling effects, coupled with dispersive scattering due to multipath propagation, can severely limit the performance of wideband systems. Just as the discrete time-frequency model can efficiently improve narrowband processing, a discrete time-scale system characterization is important in processing wideband time-varying systems. In this paper, a time-scale model is proposed as a discrete characterization of wideband time-varying systems. This representation decomposes a wideband system output into discrete time shifts and Doppler scalings on the input signal, weighted by a smoothed and sampled version of the wideband spreading function. The proposed transform-based approach uses the Mellin transform that is inherently matched to scalings to geometrically sample the scale parameter and the Fourier transform to arithmetically sample the time-delay parameter. Using this proposed model, and by properly designing the signaling and reception schemes using wavelet techniques, a joint multipath-scale diversity can be achieved over a dyadic time-scale framework in wideband wireless systems. The simulation results demonstrate that, based on the proposed model, performance can be increased by exploiting the diversity intrinsically afforded by the wideband system.

G.Matz, F. Hlawatsch, “Time-varying communication channels: fundamentals, recent developments, and open problems”, invited paper in Proceedings of the 14th European Signal Processing Conference (EUSIPCO), Florence, Italy, September 4-8, 2006.
Abstract:
In many modern wireless communication systems, the assumption of a locally time-invariant (block-fading) channel breaks down due to increased user mobility, data rates, and carrier frequencies. Fast time-varying channels feature significant Doppler spread in addition to delay spread. In this tutorial paper, we review some characterizations and sparse models of time-varying channels. We then discuss several models and methods recently proposed for communications over time-varying wireless channels, and we point out some related open problems and potential research directions.

A.R. Margetts, P. Schniter and A. Swami, “Joint scale-lag diversity in wideband mobile direct sequence spread spectrum systems”, IEEE Transactions on Wireless Communications, vol.6, no.12, pp.4308-4319, December 2007.
Abstract:
We consider the effect of mobility on a wideband direct sequence spread spectrum (DSSS) communication system, and study a scale-lag Rake receiver capable of leveraging the diversity that results from mobility. A wideband signal has a large bandwidth-to-center frequency ratio, such that the typical narrowband Doppler spread assumptions do not apply to mobile channels. Instead, we assume a more general temporal scaling phenomenon, i.e., a dilation of the transmitted signal's time support. Based on a uniform ring of scatterers model, we determine that the wideband scattering function, which quantifies the average scale spreading, has a "bathtub-shaped" scale profile. We compare the performances of a scale-lag Rake and a frequency-lag Rake, each capable of leveraging the diversity that results from mobility. Such analysis applies, for example, to ultra-wideband (UWB) radio frequency channels and underwater wideband acoustic channel

Sponsors:
Science Foundation Ireland

back to project list

Costas - Enumeration and Database, Generalization, Matlab Toolbox, Correlations

SSPG Team – K. Drakakis, K. Taylor , J. Devlin, S. Rickard

Collaborators –

Rod Gow (UCD),
Garry McGuire (UCD),
Liam O’Carroll (University of Edinburgh),
Rodrigo Caballero (UCD),
Gareth O’Brien (UCD),
John Walsh (TCD),
Sandro Mattarei (University of Trento)

Background and Motivation

Costas arrays are a square arrangement of dots and blanks, such that there is only one dot per row and column and such that no two linear segments between pairs of dots have both the same length and the same slope: in that sense, they are a special subfamily of permutation arrays. They originated as an application in RADAR and SONAR engineering, where they represent frequency hopping patterns with ideal autocorrelation properties, while further engineering applications include time synchronization, optimal encryption key distribution patterns over transmitters lying on a grid etc.

Costas arrays pose many interesting problems in pure (discrete) mathematics: Do they exist for all orders? How many Costas arrays exist for every order? How can they be constructed? The 2 construction methods available today are based on finite field techniques, and the investigation of their properties leads to many interesting mathematical problems

Goals

Settle the issue of existence of Costas arrays for all orders and compute the number of arrays in every order.
Search for Costas arrays:
- Enumerate Costas arrays by brute force in various orders using software and hardware
- Stochastic search
Generalize the Costas property to higher dimensions, to the continuum, and to triplets, quadruplets etc. of points instead of pairs.
Properties of Costas arrays:
- Symmetry of Costas arrays
- Construction of long and dense Golomb rulers
- Parity populations modulo 2 in Costas arrays
- Distance vectors present in Costas arrays
- Complexity of Costas property test
Construction of new Costas arrays through combination of known ones
Cross-correlation of Costas arrays and related problems about polynomials in finite fields (collaboration with S. Mattarei)
Relation between APN permutations on the ring of integers modulo n and Costas arrays (collaboration with G. McGuire)
Development of Costas arrays Matlab toolbox
The music of Costas arrays

Progress to Date

Costas arrays of order 27 were recently enumerated, and some first results have been obtained regarding the generalization of the Costas property in the continuum and in higher dimensions. Symmetric Golomb arrays have been completely characterized (a particular subfamily leads to dense golomb rulers), while symmetric Welch arrays were found not to exist. A novel method was developed to reduce the complexity of testing for the Costas property. Sets of distance vectors most commonly present in algebraically constructed Costas arrays were identified and studied. Stochastic searches for Costas arrays were attempted with moderate success, while the combinations tested towards creating larger ones were shown to be doomed to failure. The parity populations modulo 2 of the algebraically constructed Costas arrays were completely characterized, with the exception of Golomb arrays generated in fields of characteristic 2. Some results on families of Costas arrays with low cross-correlation are available, but some conjectures still remain. A first version of the Matlab toolbox is ready and negotiations with Mathworks are under way towards making it available. APN permutations in the ring of integers modulo n were enumerated for n up to and including 18 and some simple properties were established.

Selected Outputs

Journal publications

K. Drakakis, S. Rickard: “On the generalization of the Costas property in the continuum" (accepted for publication in Advances in Mathematics of Communications)
K. Drakakis, J. Healy, S. Rickard: “A stochastic analysis approach in the search for Costas arrays" (International Journal of Applied Mathematics and Engineering Sciences, Vol. 2, No. 1, January-June 2008, pp. 93-108)
K. Drakakis, R. Gow, S. Rickard: “Parity properties of Costas arrays defined via finite fields" (Advances in Mathematics of Communications, Vol. 1, Issue 3, Aug 2007, pp. 323-332)
K. Drakakis: “Data Mining and Costas Arrays" (Turkish Journal of Electrical Engineering & Computer Sciences, Vol. 15, Issue 1, March 2007, pp. 67-76)

Conference publications

K. Drakakis: “Higher dimensional generalizations of the Costas property" (IEEE CISS 2008)
K. Drakakis, R. Gow, S. Rickard: “Distance vectors in Costas arrays" (IEEE CISS 2008)
K. Drakakis, S. Rickard: “Costas permutations in the continuum" (IEEE CISS 2008)
K. Drakakis, R. Gow: “Two experimental pearls in Costas arrays" (IEEE CISS 2008)

Journal submissions

1. K. Drakakis, R. Gow, S. Rickard: “On the disjointness of Welch- and Golomb-Costas arrays" (submitted to Journal of Algebra and its Applications)
K. Drakakis: “Costas arrays and the extension of Lambert's function on finite fields" (submitted to SIAM Journal of Discrete Mathematics)
K. Drakakis: “Two experimental pearls in Costas arrays" (submitted to Ars Combinatoria)
K. Drakakis, R. Gow, J. Healy, S. Rickard: “Cross-Correlation Properties of Costas Arrays and their images under the Dihedral Group D4" (submitted to IEEE Transactions of Information Theory)
L. Barker, K. Drakakis, S. Rickard: “On the complexity of the Costas property check" (submitted to Proceedings of the IEEE)
K. Drakakis, S. Rickard, R. Gow: “Interlaced Costas arrays do not exist" (submitted to Advances in Mathematics of Communications)
K. Drakakis: “On the generalization of the Costas property to higher dimensions" (submitted to Combinatorica)
K. Drakakis, R. Gow, L. O'Carroll: “On the symmetry of Welch- and Golomb-constructed Costas arrays" (submitted to Discrete Mathematics)

link to full list of Publications in this area

Sponsors:
Science Foundation Ireland

back to project list