home > Publications > Search

Found 122 publications with these criteria

1. Pinto, F.; Vetterli, M.   [PintoV:10]   [published]
   Space/time-frequency processing of acoustic wave fields: theory, algorithms, and applications    
   IEEE Transactions on Signal Processing, Volume: 58 , Issue: 9 , 2010
   Consider a non-parametric representation of acoustic wave fields that consists of observing the sound pressure along a straight line or a smooth contour L defined in space. The observed data contains implicit information of the surrounding acoustic scene, both in terms of spatial arrangement of the sources and their respective temporal evolution. We show that such data can be effectively analyzed and processed in what we call the space/time-frequency representation space, consisting of a Gabor representation across the spatio-temporal manifold defined by the spatial axis L and the temporal axis t. In the presence of a source, the spectral patterns generated at L have a characteristic triangular shape that changes according to certain parameters, such as the source distance and direction, the number of sources, the concavity of L, and the analysis window size. Yet, in general, the wave fronts can be expressed as a function of elementary directional components—most notably, plane waves and far-field components. Furthermore, we address the problem of processing the wave field in discrete space and time, i.e., sampled along L and t, where a Gabor representation implies that the wave fronts are processed in a block-wise fashion. The key challenge is how to chose and customize a spatiotemporal filter bank such that it exploits the physical properties of the wave field while satisfying strict requirements such as perfect reconstruction, critical sampling, and computational efficiency. We discuss the architecture of such filter banks, and demonstrate their applicability in the context of real applications, such as spatial filtering, deconvolution, and wave field coding. [pdf]
   
   
2. Bénézit, Florence; Blondel, Vincent; Thiran, Patrick; Tsitsiklis, John; Vetterli, Martin   [BénézitBTTV:10]   [published]
   Weighted Gossip: Distributed Averaging Using Non-Doubly Stochastic Matrices     
   IEEE International Symposium on Information Theory; Austin, Texas, USA, June 13-18, 2010
   This paper presents a general class of gossip-based averaging algorithms, which are inspired from Uniform Gossip [1]. While Uniform Gossip works synchronously on complete graphs, weighted gossip algorithms allow asynchronous rounds and converge on any connected, directed or undirected graph. Unlike most previous gossip algorithms [2]?[6], Weighted Gossip admits stochastic update matrices which need not be doubly stochastic. Double-stochasticity being very restrictive in a distributed setting [7], this novel degree of freedom is essential and it opens the perspective of designing a large number of new gossip-based algorithms. To give an example, we present one of these algorithms, which we call One-Way Averaging. It is based on random geographic routing, just like Path Averaging [5], except that routes are one way instead of round trip. Hence in this example, getting rid of double stochasticity allows us to add robustness to Path Averaging.
   
   
3. Kolundzija, Mihailo; Faller, Christof; Vetterli, Martin   [KolundzijaFV:10b]   [published]
   Sound Field Recording by Measuring Gradients    
   AES 128th Convention; London, May 22-25, 2010
   Gradient based microphone arrays, the horizontal sound field's plane wave decomposition, and the corresponding circular harmonics decomposition are reviewed. Further, a general relation between directivity patterns of the horizontal sound field gradients and the circular harmonics of any order is derived. Based on this relation, a number of example differential microphone arrays are analyzed, including arrays capable of approximating the sound pressure gradients necessary for obtaining the circular harmonics up to order three.
   
   
4. Roth, T. R.; Westhoff, M. C.; Huwald, Wolf Hendrik; Huff, J. A.; Rubin, J. F.; Barrenetxea, Guillermo; Vetterli, Martin; Parriaux, Aurèle; Selker, John; Parlange, Marc   [RothWHHRBVPSP:10]   [published]
   Stream Temperature Response to Three Riparian Vegetation Scenarios by Use of a Distributed Temperature Validated Model    
   Environmental Science & Technology, vol. 44, no 6, p. 2072?2078
   Elevated in-stream temperature has led to a surge in the occurrence of parasitic intrusion proliferative kidney disease and has resulted in fish kills throughout Switzerland's waterways. Data from distributed temperature sensing (DTS) in-stream measurements for three cloud-free days in August 2007 over a 1260 m stretch of the Boiron de Morges River in southwest Switzerland were used to calibrate and validate a physically based one-dimensional stream temperature model. Stream temperature response to three distinct riparian conditions were then modeled: open, in-stream reeds, and forest cover. Simulation predicted a mean peak stream temperature increase of 0.7 degrees C if current vegetation was removed, an increase of 0.1 degrees C if dense reeds covered the entire stream reach, and a decrease of 1.2 degrees C if a mature riparian forest covered the entire reach. Understanding that full vegetation canopy cover is the optimal riparian management option for limiting stream temperature, in-stream reeds, which require no riparian set-aside and grow very quickly, appear to provide substantial thermal control, potentially useful for land-use management.
   
   
5. Martin McCormick, Yue Lu, Martin Vetterli   [McCormickLV:10]   [published]
   Learning Sparse Systems at Sub-Nyquist Rates: A Frequency-Domain Approach    
   IEEE International Conference on Acoustics, Speech, and Signal Processing; Dallas, March 14-19, 2010
   
   
   
6. Ivana Tosic, Ivana Jovanovic, Pascal Frossard, Martin Vetterli, Neb Duric   [TosicJFVD:10]   [published]
   Ultrasound tomography with learned dictionaries    
   IEEE International Conference on Acoustics, Speech, and Signal Processing; Dallas, March 14-19, 2010
   
   
   
7. Amina Chebira, Matthew Fickus, Martin Vetterli   [Chebira:FV:10]   [published]
   Frame Domain Signal Processing: Framework and Applications    
   IEEE International Conference on Acoustics, Speech, and Signal Processing; Dallas, March 14-19, 2010
   
   
   
8. Kolundzija, Mihailo; Faller, Christof; Vetterli, Martin   [KolundzijaFV:10]   [published]
   Baffled Circular Loudspeaker Array With Broadband High Directivity    
   IEEE International Conference on Acoustics, Speech, and Signal Processing; Dallas, March 14-19, 2010
   Super-directional loudspeaker arrays can be used to achieve high directivity in a limited low-frequency range. As opposed to microphone arrays, the distance between the loudspeakers has to be relatively large, resulting in aliasing starting at relatively low frequencies. On the other hand, mounting a loudspeaker on a rigid baffle (e.g., a rigid cylinder or sphere) increases its directivity with frequency. Using super-directional array techniques at low frequencies and leveraging loudspeakers' increased directivity at high frequencies enables achieving high directivity both at low and high frequencies. The design of baffled circular loudspeaker arrays and an improved beamforming procedure for achieving high directivity in a broad frequency range is described.
   
   
9. Pinto, F.; Vetterli, M.   [PintoV:10a]   [published]
   Near-field adaptive beamforming and source localization in the spacetime frequency domain    
   2010 IEEE International Conference on Acoustics, Speech and Signal Processing; Dallas, Texas, USA, March 14-19, 2010
   We revisit the topics of near-field adaptive beamforming and source localization following an alternative approach based on a spatiotemporal spectral representation of the acoustic wave field. With the proposed method, the wave field is expressed as a separable combination of the signal and spatial components that characterize the various sources in the acoustic scene. This allows beamforming operations such as beam steering and sidelobe canceling to be translated into a two-dimensional (2D) sampling problem, where the sampling kernels are derived according to a parametric model representing the 2D spectral pattern generated in the presence of a source. Conversely, the spectral pattern can be estimated from an arbitrary input through the use of parametric spectral estimation techniques, providing a novel solution to the near-field source localization problem. [pdf]
   
   
10. Ingelrest, François; Barrenetxea, Guillermo; Schaeffer, G.; Vetterli, Martin; Couach, Olivier; Parlange, Marc   [IngelrestBSVCP:10]   [published]
    SensorScope: Application-Specific Sensor Network for Environmental Monitoring    
    ACM Transactions on Sensor Networks, vol. 6, no 2, p. 1-32
    SensorScope is a turnkey solution for environmental monitoring systems, based on a wireless sensor network and resulting from a collaboration between environmental and network researchers. Given the interest in climate change, environmental monitoring is a domain where sensor networks will have great impact by providing high resolution spatio-temporal data for long periods of time. SensorScope is such a system, which has already been successfully deployed multiple times in various environments (e.g., mountainous, urban). Here, we describe the overall hardware and software architectures and especially focus on the sensor network itself. We also describe one of our most prominent deployments, on top of a rock glacier in Switzerland, which resulted in the description of a micro-climate phenomenon leading to cold air release from a rock-covered glacier in a region of high alpine risks. Another focus of this paper is the description of what happened behind the scenes to turn SensorScope from a laboratory experiment into successful outdoor deployments in harsh environments. Illustrated by various examples, we point out many lessons learned while working on the project. We indicate the importance of simple code, well suited to the application, as well as the value of close interaction with end-users in planning and running the network and finally exploiting the data.
    
    
11. Nadeau, D. F.; Brutsaert, W.; Parlange, M. B.; Bou-Zeid, E.; Barrenetxea, G.; Couach, O.; Boldi, M.-O.; Selker, J. S.; Vetterli, M.   [NadeauBPBBCBSV:09]   [published]
    Estimation of urban sensible heat flux using a dense wireless network of observations    
    Environmental Fluid Mechanics, vol. 9, no 6, p. 635-653
    The determination of the sensible heat flux over urban terrain is challenging due to irregular surface geometry and surface types. To address this, in 2006?07, a major field campaign (LUCE) took place at the École Polytechnique Fédérale de Lausanne campus, a moderately occupied urban site. A distributed network of 92 wireless weather stations was combined with routine atmospheric profiling, offering high temporal and spatial resolution meteorological measurements. The objective of this study is to estimate the sensible heat flux over the built environment under convective conditions. Calculations were based on Monin?Obukhov similarity for temperature in the surface layer. The results illustrate a good agreement between the sensible heat flux inferred from the thermal roughness length approach and independent calibrated measurements from a scintillometer located inside the urban canopy. It also shows that using only one well-selected station can provide a good estimate of the sensible heat flux over the campus for convective conditions. Overall, this study illustrates how an extensive network of meteorological measurements can be a useful tool to estimate the sensible heat flux in complex urban environments.
    
    
12. Pinto, F.; Vetterli, M.   [PintoV:09]   [published]
    Coding of spatio-temporal audio spectra using tree-structured directional filterbanks    
    2009 IEEE Workshop on Applications of Signal Processing to Audio and Acoustics; New Palz, New York, October 18-21, 2009
    We address the problem of integrating directional analysis of sound into the filterbank of a spatial audio coder, with the purpose of processing and coding with some degree of independence the plane waves traveling in different directions. A plane wave represents an elementary waveform in the spatio-temporal analysis of the sound field, the same way a complex exponential is an elementary waveform in the time domain analysis of signals. Since a two-dimensional separable filterbank is not flexible enough for this purpose, we propose a non-separable approach based on the quincunx filterbank with diamond-shaped filters, cascaded with a base transform filterbank. This solution provides an invertible and critically sampled decomposition of the spatiotemporal spectra into subbands representing the different directions of wave propagation. [pdf]
    
    
13. Kolundzija, Mihailo; Faller, Christof; Vetterli, Martin   [KolundzijaFV:09d]   [published]
    Designing Practical Filters For Sound Field Reconstruction    
    AES 127th Convention; New York, October 9-12, 2009, no Preprint 7851
    Multichannel sound field reproduction techniques, such as Wave Field Synthesis (WFS) and Sound Field Reconstruction (SFR), define loudspeaker filters in the frequency domain. However, in order to use these techniques in practical systems, one needs to convert these frequency-domain characteristics to practical and efficient time-domain digital filters. Additional limitation of SFR comes from the fact that it uses a numerical matrix pseudoinversion procedure, where the obtained filters are sensitive to numerical errors when the system matrix has a high condition number. This paper describes physically-motivated modifications of the SFR approach that allow for mitigating conditioning problems and frequency-domain loudspeaker filter smoothing that allows for designing short time-domain filters while maintaining high sound field reproduction accuracy. It also provides comparisons of sound field reproduction accuracy of WFS and SFR using the obtained discrete-time filters.
    
    
14. Amin Karbasi; Ali Hormati; Soheil Mohajer; Martin Vetterli   [KarbasiHMV:09]   [published]
    Support recovery in compressed sensing: An estimation theoretic approach    
    IEEE International Symposium on Information Theory (ISIT09), Seoul, 28 June - 3 July 09
    
    
    
15. Hormati, Ali; Roy, Olivier; Lu, Yue M.; Vetterli, Martin   [HormatiRLV:09]   [published]
    Distributed Sensing of Sparse Signals under a Sparse Filtering Model    
    8th International Conference on Sampling Theory and Applications (SAMPTA); Marseille, France, May 18-22, 2009
    We consider the task of recovering correlated vectors at a central decoder based on fixed linear measurements obtained by distributed sensors. Two different scenarios are considered: In the case of universal reconstruction, we look for a sensing and recovery mechanism that works for all possible signals, whereas in the case of almost sure reconstruction, we allow to have a small set (with measure zero) of unrecoverable signals. We provide achievability bounds on the number of samples needed for both scenarios. The bounds show that only in the almost sure setup can we effectively exploit the signal correlations to achieve effective gains in sampling efficiency. In addition, we propose an efficient and robust distributed sensing and reconstruction algorithm based on annihilating filters.
    
    
16. Kolundzija, Mihailo; Faller, Christof; Vetterli, Martin   [KolundzijaFV:09]   [published]
    Spatio-Temporal Gradient Analysis of Differential Microphone Arrays    
    AES 126th Convention; Munich, May 7-10, 2009, no Preprint 7772
    The literature on gradient and differential microphone arrays makes a distinction between the two types, and nevertheless shows how both types can be used to obtain the same directional responses. A more theoretically sound rationale for using delays in differential microphone arrays has not yet been given. This paper presents a gradient analysis of the sound field viewed as a spatio-temporal phenomenon, and gives a theoretical interpretation of the working principles of gradient and differential microphone arrays. It shows that both types of microphone arrays can be viewed as devices for approximately measuring spatio-temporal derivatives of the sound field. Furthermore, it also motivates the design of high-order differential microphone arrays using the aforementioned spatio-temporal gradient analysis.
    
    
17. Kolundzija, Mihailo; Faller, Christof; Vetterli, Martin   [KolundzijaFV:09b]   [published]
    Sound Field Reconstruction: An Improved Approach For Wave Field Synthesis    
    AES 126th Convention; Munich, May 7-10, 2009, no Preprint 7754
    Wave field synthesis (WFS) is a prevalent approach to multiple-loudspeaker sound reproduction for an extended listening area. Although powerful as a theoretical concept, its deployment is hampered by practical limitations due to diffraction, aliasing, and the effects of the listening room. Reconstructing the desired sound field in the listening area, accounting for the medium propagation characteristic, is another approach termed as sound field reconstruction (SFR). It is based on the essential band-limitedness of the sound field, which enables a continuous matching of the reconstructed and the desired sound field by their matching on a discrete set of points spaced below the Nyquist distance. We compare the two approaches in a common single-source free-field setup, and show that SFR provides improved sound field reproduction compared to WFS in a wide listening area around a defined reference line.
    
    
18. Lu, Yue M.; Vetterli, Martin   [LuV:09]   [published]
    Spatial Super-Resolution of a Diffusion Field by Temporal Oversampling in Sensor Networks    
    IEEE International Conference on Acoustics, Speech and Signal Processing; Taipei, Taiwan, April 19-24, 2009, p. 2249-2252
    We study the spatial-temporal sampling of a linear diffusion field, and show that it is possible to compensate for insufficient spatial sampling densities by oversampling in time. Our work is motivated by the following issue often encountered in sensor network sampling, namely increasing the temporal sampling density is often easier and less expensive than increasing the spatial sampling density of the network. For the case of sampling a diffusion field, we show that, to achieve trade-off between spatial and temporal sampling, the spatial arrangement of the sensors must satisfy certain conditions. We provide in this paper the precise relationships between the achievable reduction of spatial sampling density, the required temporal oversampling rate, the spatial arrangement of the sensors, and the bound for the condition numbers of the resulting sampling and reconstruction procedures.
    
    
19. Roy, Olivier; Hormati, Ali; Lu, Yue M.; Vetterli, Martin   [RoyHLV:09]   [published]
    Distributed Sensing of Signals Linked by Sparse Filtering    
    IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP); Taiwan, April 19-24, 2009, p. 2409-2412
    We consider the task of recovering correlated vectors at a central decoder based on fixed linear measurements obtained by distributed sensors. A general formulation of the problem is proposed, under both a universal and an almost sure reconstruction requirement. We then study a specific correlation model which involves a filter that is sparse in the time domain. While this sparsity assumption does not allow reducing the description cost in the universal case, we show that large gains can be achieved in the almost sure scenario by means of a novel distributed scheme based on annihilating filters. The robustness of the proposed method is also investigated.
    
    
20. Florence Benezit, Patrick Thiran, Martin Vetterli   [BenezitTV:09]   [published]
    INTERVAL CONSENSUS: FROM QUANTIZED GOSSIP TO VOTING    
    IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP); Taiwan, April 19-24, 2009
    
    
    
21. Luciano Sbaiz, Feng Yang, Edoardo Charbon, Sabine Süsstrunk, Martin Vetterli   [SbaizYCSV:09]   [published]
    THE GIGAVISION CAMERA    
    IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP); Taiwan, April 19-24, 2009
    
    
    
22. Hormati, Ali; Roy, Olivier; Lu, Yue M.; Vetterli, Martin   [HormatiRLV:09b]   [published]
    Distributed Sampling of Correlated Signals Linked by Sparse Filtering: Theory and Applications    
    IEEE Transactions on Signal Processing, vol. 58, no 3, p. 1095 - 1109
    We study the distributed sampling and centralized reconstruction of two correlated signals, modeled as the input and output of an unknown sparse filtering operation. This is akin to a Slepian-Wolf setup, but in the sampling rather than the lossless compression case. Two different scenarios are considered: In the case of universal reconstruction, we look for a sensing and recovery mechanism that works for all possible signals, whereas in what we call almost sure reconstruction, we allow to have a small set (with measure zero) of unrecoverable signals. We derive achievability bounds on the number of samples needed for both scenarios. Our results show that, only in the almost sure setup can we effectively exploit the signal correlations to achieve effective gains in sampling efficiency. In addition to the above theoretical analysis, we propose an efficient and robust distributed sampling and reconstruction algorithm based on annihilating filters. Finally, we evaluate the performance of our method in one synthetic scenario, and two practical applications, including the distributed audio sampling in binaural hearing aids and the efficient estimation of room impulse responses. The numerical results confirm the effectiveness and robustness of the proposed algorithm in both synthetic and practical setups.
    
    
23. Schaefer, Gunnar; Ingelrest, François; Vetterli, Martin   [SchaeferIV:08]   [published]
    Potentials of Opportunistic Routing in Energy-Constrained Wireless Sensor Networks    
    The 6th European Conference on Wireless Sensor Networks (EWSN 2009); Cork, Ireland, February 11-13, 2009
    The low quality of wireless links leads to perpetual packet losses. While an acknowledgment mechanism is generally used to cope with these losses, multiple retransmissions nevertheless occur. Opportunistic routing limits these retransmissions by taking advantage of the broadcast nature of the wireless channel: sending packets to multiple receivers at once, and only then, based on the outcome, choosing the actual next hop. In this paper, we first study the potentials of opportunistic routing in energy-constrained wireless sensor networks. In particular, the reduction of retransmissions due to the broadcast advantage is balanced with the arising need for coordination to avoid duplicate packets. We then propose Coordinated Anypath Routing, an opportunistic routing protocol designed for wireless sensor networks, in which the coordination between receivers is handled by an overhearing-based acknowledgment scheme. Our protocol may be used to minimize either retransmissions or power consumption, and our simulation results show that, with lossy links, energy savings go up to 7%, even for small networks of 20 nodes.
    
    
24. Dragoti, P. L.; Gastpar, M.; Roy, Olivier; Ajdler, Thibaut; Konsbruck, Robert L.; Vetterli, Martin   [RoyAKV:08]   [published]
    Distributed Compression in Microphone Arrays    
    Distributed Source Coding: Theory, Algorithms and Applications
    
    
    
25. Barrenetxea, Guillermo; Ingelrest, François; Schaefer, Gunnar; Vetterli, Martin   [BarrenetxeaISV:08]   [published]
    The Hitchhiker's Guide to Successful Wireless Sensor Network Deployments    
    The 6th ACM Conference on Embedded Networked Sensor Systems (SenSys 2008); Raleigh, NC, USA, 5-7 November 2008, p. 43-56
    The successful deployment of a wireless sensor network is a difficult task, littered with traps and pitfalls. Even a functional network does not guarantee gathering meaningful data. In SensorScope, with its high-mountain campaigns, we have acquired invaluable experience in planning, conducting, and managing real-life sensor network deployments. In this paper, we share our knowledge by stepping through the entire process, from the preparatory hard- and software development to the actual field deployment. Illustrated by numerous real-life examples, excerpted from our own experience, we point out many potential problems along this way and their possible solutions.
    
    
26. P. Prandoni, M. Vetterli   [PrandoniV:08]   [published]
    Signal Processing for Communications    
    EPFL Press, Sep 2008
    
    
    
27. Pinto, F.; Vetterli, M.   [PintoV:08f]   [published]
    Bitstream format for spatio-temporal wave field coder    
    Audio Engineering Society 124th Convention; Amsterdam, The Netherlands, 2008
    
    
    
28. Barrenetxea, Guillermo; Ingelrest, François; Schaefer, Gunnar; Vetterli, Martin; Couach, Olivier; Parlange, Marc   [BarrenetxeaISVCP:08]   [published]
    SensorScope: Out-of-the-Box Environmental Monitoring    
    The 7th ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN 2008); St. Louis, MO, USA, 22-24 April 2008, p. 332-343
    An important field of application for wireless sensor networks is environmental monitoring. Given the importance of potential climate changes, environmental impact on cities, and pollution, it is an application domain where sensor networks can have great impact and as such is getting more and more attention. Current data collection techniques are indeed rather limited and make use of very expensive sensing stations, leading to a lack of appropriate observations. In this paper, we present SensorScope, a collaborative project between environmental and network researchers, that aims at providing an efficient and cheap out-of-the-box environmental monitoring system based on a wireless sensor network. We especially focus on data gathering and present the hardware and network architecture of SensorScope. We also describe a real-world deployment, which took place on a rock glacier in Switzerland, as well as the results we obtained.
    
    
29. Denantes, Patrick; Benezit, Florence; Thiran, Patrick; Vetterli, Martin   [DenantesBTV:08]   [published]
    Which Distributed Averaging Algorithm Should I Choose for my Sensor Network?    
    IEEE INFOCOM 2008; Phoenix, AZ, 13-18 April 2008
    Average consensus and gossip algorithms have recently received significant attention, mainly because they constitute simple and robust algorithms for distributed information processing over networks. Inspired by heat diffusion, they compute the average of sensor networks measurements by iterating local averages until a desired level of convergence. Confronted with the diversity of these algorithms, the engineer may be puzzled in his choice for one of them. As an answer to his/her need, we develop precise mathematical metrics, easy to use in practice, to characterize the convergence speed and the cost (time, message passing, energy...) of each of the algorithms. In contrast to other works focusing on time-invariant scenarios, we evaluate these metrics for ergodic time- varying networks. Our study is based on Oseledec?s theorem, which gives an almost-sure description of the convergence speed of the algorithms of interest. We further provide upper bounds on the convergence speed. Finally, we use these tools to make some experimental observations illustrating the behavior of the convergence speed with respect to network topology and reliability in both average consensus and gossip algorithms.
    
    
30. Roy, Olivier; Vetterli, Martin   [RoyV:08b]   [published]
    Dimensionality Reduction for Distributed Estimation in the Infinite Dimensional Regime    
    IEEE Transactions on Information Theory, vol. 54, no 2, p. 1655-1669
    Distributed estimation of an unknown signal is a common task in sensor networks. The scenario usually envisioned consists of several nodes, each making an observation correlated with the signal of interest. The acquired data is then wirelessly transmitted to a central reconstruction point that aims at estimating the desired signal within a prescribed accuracy. Motivated by the obvious processing limitations inherent to such distributed infrastructures, we seek to find efficient compression schemes that account for limited available power and communication bandwidth. In this paper, we propose a transform-based approach to this problem where each sensor provides the central reconstruction point with a low-dimensional approximation of its local observation by means of a suitable linear transform. Under the mean-squared error criterion, we derive the optimal solution to apply at one sensor assuming all else being fixed. This naturally leads to an iterative algorithm whose optimality properties are exemplified using a simple though illustrative correlation model. The stationarity issue is also investigated. Under restrictive assumptions, we then provide an asymptotic distortion analysis, as the size of the observed vectors becomes large. Our derivation relies on a variation of the Toeplitz distribution theorem which allows to provide a reverse "water-filling" perspective to the problem of optimal dimensionality reduction. We illustrate, with a first-order Gauss-Markov model, how our findings allow to compute analytical closed-form distortion formulas that provide an accurate estimation of the reconstruction error obtained in the finite dimensional regime. [pdf]
    
    
31. Barrenetxea, Guillermo; Ingelrest, François; Lu, Yue M.; Vetterli, Martin   [BarrenetxeaILV:08]   [published]
    Assessing the Challenges of Environmental Signal Processing through the SensorScope Project    
    The 33rd IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2008); The 33rd International Conference on Acoustics, Speech, and Signal Processing (ICASSP)
    SensorScope is a collaborative project between network, signal processing, and environmental researchers that aims at providing a cheap and out-of-the-box environmental monitoring system based on a wireless sensor network. It has been successfully used in a number of deployments to gather hundreds of megabytes of environmental data. With data gathering techniques well mastered, the efficient processing of the huge amounts of the acquired information to allow for useful exploitation has become an increasingly important issue. In this paper, we present a number of challenging and relevant signal processing tasks that arise from the SensorScope project. We believe the resolution of these problems will benefit from a better understanding of the underlying physical processes. We show an example to demonstrate how physical correlations between different sensing modalities can help reduce the sampling rate.
    
    
32. Pinto, F.; Vetterli, M.   [PintoV:08g]   [published]
    Wave field coding in the spacetime frequency domain    
    2008 IEEE International Conference on Acoustics, Speech, and Signal Processing; Las Vegas, USA, 2008
    
    
    
33. Ingelrest, François; Barrenetxea, Guillermo; Vetterli, Martin   [IngelrestBV:08]   [published]
    SensorScope, un système clef en main de surveillance de l'environnement    
    13ème Colloque Francophone sur l'Ingénierie des Protocoles (CFIP 2008); Les Arcs, France, 25-28 March 2008
    Given the importance of climate changes and their potentially dramatic consequences for human beings, designing precise and reliable evolution models is of prime importance. Unfortunately, current data collection techniques are rather limited as they make use of huge and very expensive sensing stations, leading to a lack of dense spatial and temporal observations. Wireless sensor networks are an alternative solution well-fitted to this problem, and may as such have a considerable impact on this domain. In this paper, we present SensorScope, a multidisciplinary project that aims at providing such an ''out-of-the-box'' monitoring system, from the sensing stations to the data management infrastructure. Here we especially focus on data gathering and on the communication protocols used for this task. We also describe one of our deployments, carried out during two months on a rock glacier in Switzerland, which led to the modeling of a micro climate that plays an important role in dangerous mud streams.
    
    
34. Barrenetxea, Guillermo; Ingelrest, François; Schaefer, Gunnar; Vetterli, Martin   [BarrenetxeaISGV:08]   [published]
    Wireless Sensor Networks for Environmental Monitoring: The SensorScope Experience    
    The 20th IEEE International Zurich Seminar on Communications (IZS 2008); Zurich, Switzerland, 12-14 March 2008
    While wireless sensor networks have been extensively studied in the past few years, most results are of theoretical nature and were obtained outside of a practical context. This can be problematic for real applications, especially in the area of environmental monitoring where many factors, such as harsh weather conditions, can greatly influence the performance of such a network, while reliable delivery and high-quality measurements are required. SensorScope is an interdisciplinary project, elaborated by environmental and networking researchers, that aims at narrowing the gap between theory and practice. Several successful real-world deployments have already been undertaken in rugged environments. In this paper, we analyze the particular requirements of environmental monitoring and how these requirements have been met in the SensorScope project. We also present an application example of a deployment, undertaken in a harsh mountain environment.
    
    
35. Ajdler, Thibaut; Faller, Christof; Sbaiz, Luciano; Vetterli, Martin   [AjdlerFSV:08]   [published]
    Sound Field Analysis Along a Circle and its Application to HRTF Interpolation    
    Journal of the Audio Engineering Society, vol. 56, no 3, p. 156-175
    The sampling and interpolation of a sound field in two and three dimensions along a circle is discussed. The Fourier domain representation of the sound field is used, and an angular sampling theorem is developed for the sampling of the sound field along a circle. Based on these results, HRTF sampling and interpolation are discussed. This method achieves very precise interpolation in terms of mean square error. However, these results are only possible if very finely spaced HRTF measurements are available. A method is proposed to improve interpolation results when the HRTF measurements are more coarsely spaced than dictated by the angular Nyquist theorem. The proposed method interpolates the HRTFs in a subband domain. In subbands where small angular aliasing occurs, the previous method is applied. In the other subbands, interpolation is carried out in a complex temporal envelope domain to avoid aliasing. Simulations with models and measured data show that the proposed algorithm performs significantly better than previous methods in a mean square error sense.
    
    
36. K. Aberer, G. Alonso, G. Barrenetxea, J. Beutel, J. Bovay, H. Dubois-Ferrière, D. Kossmann, M. Parlange, L. Thiele, M. Vetterli   [AbererABBBDKPTV:07b]   [published]
    Notre environnement devient intelligent    
    Bulletin electrosuisse, 21/2007, Nov 07
    
    
    
37. Sbaiz, Luciano; Vandewalle, Patrick; Vetterli, Martin   [SbaizVV:07]   [published]
    Groebner Basis Methods for Multichannel Sampling with Unknown Offsets    
    Applied and Computational Harmonic Analysis, vol. 25, no 3, p. 277-294
    In multichannel sampling, several sets of sub-Nyquist sampled signal values are acquired. The offsets between the sets are unknown, and have to be resolved, just like the parameters of the signal itself. This problem is nonlinear in the offsets, but linear in the signal parameters. We show that when the basis functions for the signal space are related to polynomials, we can express the joint offset and signal parameter estimation as a set of polynomial equations. This is the case for example with polynomial signals or Fourier series. The unknown offsets and signal parameters can be computed exactly from such a set of polynomials using Gröbner bases and Buchberger's algorithm. This solution method is developed in detail after a short and tutorial overview of Gröbner basis methods. We then address the case of noisy samples, and consider the computational complexity, exploring simplifications due to the special structure of the problem. [pdf]
    
    
38. Gastpar, M.; Dragotti, P. L.; Vetterli, M.   [GastparDV:07]   [published]
    Correction to "The Distributed Karhunen–Loève Transform"    
    IEEE Transactions on Information Theory, Volume 53, Issue 11, Nov 2007
    
    
    
39. Roy, Olivier; Vetterli, Martin   [RoyV:07b]   [published]
    Distributed Spatial Audio Coding in Wireless Hearing Aids    
    IEEE Workshop on Applications of Signal Processing to Audio and Acoustics (WASPAA); Mohonk Mountain House, New Paltz, NY, USA, October 21-24, 2007, p. 227-230
    The information content of binaural signals can be beneficial to many algorithms deployed in current digital hearing aids. However, the exchange of such signals over a wireless communication link requires transmission schemes that must fulfill demanding technical constraints. We present a distributed coding algorithm that builds on psychoacoustic principles in order to achieve this goal with low bitrates, while preserving affordable complexity. The key steps of the proposed algorithm are detailed and the accuracy of the signal exchange mechanism is evaluated in simple simulated acoustic scenarios.
    
    
40. Jovanovic, Ivana; Sbaiz, Luciano; Vetterli, Martin   [JovanovicSV:07]   [published]
    Tomographic approach for parametric estimation of local diffusive sources and application to heat diffusion    
    IEEE International Conference on Image Processing; San Antonio, Texas, September 16-19, vol. 4, p. 153-156
    We consider localized instantaneous sources that reside in a 2D diffusive environment. Our goal is to reconstruct the induced field from the measurements obtained by distributed sensors. Although the field is non-bandlimited, we capitalize on the fact that it is completely determined by a finite number of parameters to develop a method that allows perfect reconstruction. We demonstrate how these results can be applied in practice in the particular case of heat diffusion. Simulation results confirm the effectiveness of the method. [pdf]
    
    
41. Roy, Olivier; Vetterli, Martin   [RoyV:07a]   [published]
    The Effective Rank: A Measure of Effective Dimensionality    
    European Signal Processing Conference (EUSIPCO); Poznan, Poland, September 3-7, 2007, p. 606-610
    Many signal processing algorithms include numerical problems where the solution is obtained by adjusting the value of parameters such that a specific matrix exhibits rank deficiency. Since rank minimization is generally not practicable owing to its integer nature, we propose a real-valued extension that we term effective rank. After proving some of its properties, the effective rank is provided with an operational meaning using a result on the coefficient rate of a stationary random process. Finally, the proposed measure is assessed in a practical scenario and other potential applications are suggested. [pdf]
    
    
42. Jovanovic, Ivana; Hormati, Ali; Sbaiz, Luciano; Vetterli, Martin   [JovanovicHSV:07]   [published]
    Efficient and Stable Acoustic Tomography Using Sparse Reconstruction Methods    
    19th International Congress on Acoustics; Madrid, 2-7 September 2007
    We study an acoustic tomography problem and propose a new inversion technique based on sparsity. Acoustic tomography observes the parameters of the medium that influence the speed of sound propagation. In the human body, the parameters that mostly influence the sound speed are temperature and density, in the ocean - temperature and current, in the atmosphere - temperature and wind. In this study, we focus on estimating temperature in the atmosphere using the information on the average sound speed along the propagation path. The latter is practically obtained from travel time measurements. We propose a reconstruction algorithm that exploits the concept of sparsity. Namely, the temperature is assumed to be a linear combination of some functions (e.g. bases or set of different bases) where many of the coefficients are known to be zero. The goal is to find the non-zero coefficients. To this end, we apply an algorithm based on linear programming that under some constrains finds the solution with minimum l0 norm. This is actually equivalent to the fact that many of the unknown coefficients are zeros. Finally, we perform numerical simulations to assess the effectiveness of our approach. The simulation results confirm the applicability of the method and demonstrate high reconstruction quality and robustness to noise. [pdf]
    
    
43. Vandewalle, Patrick; Sbaiz, Luciano; Vandewalle, Joos; Vetterli, Martin   [VandewalleSVV:07]   [published]
    Super-Resolution from Unregistered and Totally Aliased Signals Using Subspace Methods    
    IEEE Transactions on Signal Processing, vol. 55, no 7, Part 2, p. 3687-3703
    In many applications, the sampling frequency is limited by the physical characteristics of the components: the pixel pitch, the rate of the A/D converter, etc. A low-pass filter is then often applied before the sampling operation to avoid aliasing. However, when multiple copies are available, it is possible to use the information that is inherently present in the aliasing to reconstruct a higher resolution signal. If the different copies have unknown relative offsets, this is a non-linear problem in the offsets and the signal coefficients. They are not easily separable in the set of equations describing the super-resolution problem. Thus, we perform joint registration and reconstruction from multiple unregistered sets of samples. We give a mathematical formulation for the problem when there are M sets of N samples of a signal that is described by L expansion coefficients. We prove that the solution of the registration and reconstruction problem is generically unique if MN>= L+M-1. We describe two subspace-based methods to compute this solution. Their complexity is analyzed, and some heuristic methods are proposed. Finally, some numerical simulation results on one and two-dimensional signals are given to show the performance of these methods. [pdf]
    
    
44. T. Ajdler, L. Sbaiz, A. Ridolfi, and M. Vetterli   [AjdlerSRV:07]   [submitted]
    Spatio-Temporal Channels From the Wave Equation Have Butterfly Spectra    
    IEEE Transactions on Signal Processing
    Multipath channels between moving senders and receivers are of interest in many signal processing and communications scenarios, from acoustic echo cancellation to wireless mobile communications. Two physical constraints characterize these channels: (i) propagation is governed by the wave equation, (ii) movements of sender and / or receiver are smooth and slow as compared to propagation. In this paper, we show that the resulting time-varying impulse response has a butterfly shaped spectrum, that is, its spatial bandwidth increases linearly with temporal frequency. The method to show this uses smooth trajectories given by continuous-time autoregressive processes, in order to generate a suitable stochastic process corresponding to time-varying impulse responses. The power spectrum of such a process can be evaluated explicitly in certain simple cases and approximated in more general cases. The distinguishing features of the power spectrum is its essential butterfly shape and the widening of the shape as a function of the speed of movement. We specifically derive a Carson's like approximation rule that predicts the butterfly's bandwidth as a function of the parameters of the movement and of the channel. Experimental results in both the acoustic and the electro-magnetic case verify the established shape of the power spectra. Both the theoretical and experimental results are relevant for modeling of wideband channels (e.g. acoustic or ultra-wide band), since they predict the "variation bandwidth" as a function of temporal frequency. This in turn is important for channel adaptation, equalization and power allocation.
    
    
45. Ajdler, Thibaut; Sbaiz, Luciano; Vetterli, Martin   [AjdlerSV:07]   [published]
    Dynamic Measurement of Room Impulse Responses using a Moving Microphone    
    Journal of the Acoustical Society of America, vol. 122, no 3
    A novel technique for the recording of large sets of room impulse responses or head-related transfer functions is presented. The technique uses a microphone or a loudspeaker moving with constant speed. Given a setup (e.g. length of the room impulse response), a careful choice of the recording parameters (excitation signal, speed of movement) is shown to lead to the reconstruction of all impulse responses along the trajectory. In the case of moving element along a circle, the maximal angular speed is given in function of the length of the impulse response, its maximal temporal frequency, the speed of sound propagation and the radius of the circle. As result of this theory, it is shown that head-related transfer functions sampled at $44.1~$kHz can be measured at all angular positions along the horizontal plane in less than one second. The presented theory is compared with a real system implementation using a precision moving microphone holder. The practical setup is discussed together with its limitations.
    
    
46. Vandewalle, Patrick; Barrenetxea, Guillermo; Jovanovic, Ivana; Ridolfi, Andrea; Vetterli, Martin   [VandewalleBJRV:07]   [published]
    Experiences with Reproducible Research in Various Facets of Signal Processing Research    
    IEEE Conference on Acoustics, Speech and Signal Processing, vol. 4, p. 1253-1256
    How often have you been able to implement an algorithm as it is described in a paper? And when you did, were you confident that you had exactly the same parameter values and results as the authors of the paper? All too often, articles do not describe all the details of an algorithm and thus prohibit an implementation by someone else. In this paper, we describe our experience with reproducible research, a paradigm to allow other people to reproduce with minimal effort the results we have obtained. We discuss both the reproducibility of data and algorithms, and give examples for each of them. The effort required to make research reproducible is compensated by a higher visibility and impact of the results. [pdf]
    
    
47. Aberer, Karl; Alonso, Gustavo; Barrenetxea, Guillermo; Beutel, Jan; Bovay, Jacques; Dubois-Ferrière, Henri; Kossmann, Donald; Parlange, Marc; Thiele, Lothar; Vetterli, Martin   [AbererABBBDKPTV:07]   [published]
    Infrastructures for a Smart Earth - The Swiss NCCR-MICS initiative    
    PIK - Praxis der Informationsverarbeitung und Kommunikation, vol. 30. Jahrgang, no Heft 1, p. 20-25
    The Swiss National Competence Center for Research in Mobile Information and Communication Systems (NCCR MICS or MICS) is a research initiative sponsored by the Swiss National Science Foundation to promote long term research projects in areas of vital strategic importance for Switzerland. The NCCR MICS covers a wide spectrum of topics in the area of mobile information and communication systems, ranging from information theory related to ad-hoc sensor networks to business models for pervasive computing, including network and routing issues, software and application development, and actual deployments of sensor networks. In this paper, we briefly present MICS as a whole, describe a major application in the area of environmental monitoring and discuss in some detail the hardware and software platforms developed in the Center.
    
    
48. G. Barrenetxea, M. Bystranowski, O. Couach, H. Dubois-Ferrière, M. Krichane, T. Varidel, S. Mortier, J. Mezzo, S. Dufey, J. Selker, G. Schaefer, M. Parlange and M. Vetterli   [BarrenetxeaBCDKVMMDSSP:07]   [published]
    SensorScope: An Urban Environmental Monitoring Network (demo)    
    European conference on Wireless Sensor Networks (EWSN), Delft, 29-31 Jan 07
    The SensorScope project is a collaboration between environmental scientists and hardware/software engineers at Ecole Polytechnique Federale de Lausanne (EPFL) that aims at better understanding the turbulent subgrid-scale physics in an urban environment. SensorScope consists in a Wireless Sensor Network (WSN) of 110 nodes (weather stations) deployed at the university campus of EPFL. This network measures key environmental quantities at high spatial and time resolution for the purpose of modeling the influence of ground heterogeneity on meteorological parameters at local scale.
    
    
49. Vandewalle, Patrick; Sbaiz, Luciano; Vandewalle, Joos; Vetterli, Martin   [VandewalleSVV:06a]   [published]
    Aliasing is Good for You: Joint Registration and Reconstruction for Super-Resolution    
    EPFL Technical Report, 2006
    In many applications, the sampling frequency is limited by the physical characteristics of the components: the pixel pitch, the rate of the A/D converter, etc. A low-pass filter is then often applied before the sampling operation to avoid aliasing. However, when multiple copies are available, it is possible to use the information that is inherently present in the aliasing to reconstruct a higher resolution signal. If the different copies have unknown relative offsets, this is a non-linear problem in the offsets and the signal coefficients. They are not easily separable in the set of equations describing the super-resolution problem. Thus, we perform joint registration and reconstruction from multiple unregistered sets of samples. We give a mathematical formulation for the problem when there are M sets of N samples of a signal that is described by L expansion coefficients. We prove that the solution of the registration and reconstruction problem is generically unique if MN >= L+M-1. We describe two subspace-based methods to compute this solution. Their complexity is analyzed, and some heuristic methods are proposed. Finally, some numerical simulation results on one and two-dimensional signals are given to show the performance of these methods. [pdf]
    
    
50. Gastpar, Michael; Dragotti, Pier Luigi; Vetterli, Martin   [GastparDV:06]   [published]
    The Distributed Karhunen-Loève Transform    
    IEEE Transactions on Information Theory, vol. 52, no 12, p. 5177-5196
    The Karhunen-Loeve transform (KLT) is a key element of many signal processing and communication tasks. Many recent applications involve distributed signal processing, where it is not generally possible to apply the KLT to the entire signal; rather, the KLT must be approximated in a distributed fashion. This paper investigates such distributed approaches to the KLT, where several distributed terminals observe disjoint subsets of a random vector.
    
    
51. Ajdler, Thibaut; Sbaiz, Luciano; Vetterli, Martin   [AjdlerSV:06]   [published]
    The Plenacoustic Function and its Sampling    
    IEEE Transactions on Signal Processing, vol. 54, no 10, p. 3790-3804
    
    
    
52. G. Barrenetxea, B. Beferull-Lozano, M. Vetterli   [BarrenetxeaBV:06]   [published]
    Correction to “Lattice Networks: Capacity Limits, Optimal Routing, and Queueing Behavior”    
    IEEE/ACM Transactions on Networking, vol 14, no 5, Oct 2006
    
    
    
53. Ajdler, Thibaut; Konsbruck, Robert Lee; Roy, Olivier; Sbaiz, Luciano; Telatar, Emre; Vetterli, Martin   [AjdlerKRSTV:06]   [published]
    Spatio-Temporal Sampling and Distributed Compression of the Sound Field    
    European Signal Processing Conference (EUSIPCO); Florence, Italy, September 4-8, 2006
    We investigate how the sound field induced by an acoustic event evolves over space and time. The characteristics of its bidimensional Fourier spectrum are analyzed and spatio-temporal sampling results using an array of microphones are provided for different scenarios of interest. We then address the distributed compression problem using an information-theoretic point of view. In this context, optimal rate-distortion tradeoffs are derived for two scenarios of interest. A linear network setup is first considered, where a central base station aims at recovering with minimum distortion the signals recorded by an infinite line of microphones. A hearing aid problem is then studied, where two hearing devices exchange data over a rate-constrained wireless link in order to provide spatial noise reduction. [pdf]
    
    
54. Dubois-Ferriere, Henri; Vetterli, Martin; Grossglausser, Matthias   [Dubois-Ferriere:06]   [published]
    Anypath routing    
    PhD thesis EPFL, accepted in Sep 2006 (Prof. M. Vetterli)
    
    
    
55. Jovanovic, Ivana; Sbaiz, Luciano; Vetterli, Martin   [JovanovicSV:06b]   [published]
    Acoustic tomography for estimating temperature and wind flow    
    13th International Symposium for the Advancement of Boundary Layer Remote Sensing, ISARS; Garmisch-Partenkirchen, Germany, July 18-20, 2006, p. 69-71
    We consider the problem of reconstructing superimposed temperature and wind flow fields from acoustic measurements. A new technique based solely on acoustic wave propagation is presented. In contrast to the usual straight ray assumption, a bent ray model is considered in order to achieve higher accuracy. We also develop a lab size experiment for temperature estimation. [pdf]
    
    
56. Roy, Olivier; Vetterli, Martin   [RoyV:06c]   [published]
    Rate-Constrained Beamforming for Collaborating Hearing Aids    
    International Symposium on Information Theory (ISIT); Seattle, WA, USA, July 9-14, 2006, p. 2809-2813
    Hearing aids are audio capture devices which aim at providing the hearing impaired with better audibility. Most of the state-of-the-art systems involve sensing devices that work independently. However, the availability of a wireless communication link between two hearing aids would allow to perform spatial beamforming such as to provide better rejection of interfering signals. In this paper, we identify and study the above scenario from an information-theoretic viewpoint. We explore the gain provided by collaborating hearing aids as a function of the communication rate. In particular, we derive a closed-form gain-rate formula in the case where a sound source has to be extracted from ambient noise. A similar analysis is provided in the presence of an interfering point source and the corresponding optimal rate allocation is discussed. [pdf]
    
    
57. Grossglauser, M.; Vetterli, M.   [GrossglauserV:06]   [published]
    Locating Mobile Nodes with EASE: Learning Efficient Routes from Encounter Histories Alone    
    IEEE/ACM Transactions on Networking, vol. 14, no 3, p. 457-469
    Routing in large-scale mobile ad hoc networks is challenging because all the nodes are potentially moving. Geographic routing can partially alleviate this problem, as nodes can make local routing decisions based solely on the destinations' geographic coordinates. However, geographic routing still requires an efficient {\em location service}, i.e., a distributed database recording the location of every destination node. Devising efficient, scalable, and robust location services has received considerable attention in recent years. The main purpose of this paper is to show that {\em node mobility} can be exploited to disseminate destination location information {\em without incurring any communication overhead}. We achieve this by letting each node maintain a local database of the time and location of its last encounter with every other node in the network. This database is consulted by packets to obtain estimates of their destination's current location. As a packet travels towards its destination, it is able to successively refine an estimate of the destination's precise location, because node mobility has ``diffused'' estimates of that location. We define and analyze a very simple algorithm called EASE (Exponential Age Search) and show that in a model where $\Theta(n)$ nodes perform independent random walks on a square lattice of size $n$, the length of the routes computed by EASE are of the same order as the distance between the source and destination {\em even for very large $n$.} Therefore, without disseminating any explicit location information, the length of EASE routes are within a constant factor of routes obtained with perfect information. We discuss refinements of the EASE algorithm and evaluate it through extensive simulations. We discuss general conditions such that the mobility diffusion effect leads to efficient routes without an explicit location service. In practical settings, where these conditions may not always be met, we believe that the mobility diffusion effect can complement existing location services and enhance their robustness and scalability. [pdf]
    
    
58. Guillermo Barrenechea, Baltasar Beferull-Lozano, Martin Vetterli   [BarrenecheaBV:06b]   [published]
    Lattice Sensor Networks: Capacity Limits and Optimal Routing    
    IEEE/ACM Trans. Netw., vol. 14, no. 3, June 2006
    
    
    
59. Ajdler, Thibaut; Sbaiz, Luciano; Vetterli, Martin   [AjdlerSV:06]   [published]
    Room impulse responses measurement using a moving microphone    
    120th Convention of the AES
    In this paper, we present a technique to record a large set of room impulse responses using a microphone moving along a tra jectory. The technique processes the signal recorded by the microphone to reconstruct the signals that would have been recorded at all possible spatial positions along the array. The speed of movement of the microphone is shown to be the key factor for the reconstruction. This fast method of recording spatial impulse responses can also be applied for the recording of head-related transfer functions. [pdf]
    
    
60. Vandewalle, Patrick; Sbaiz, Luciano; Vetterli, Martin   [VandewalleSV:06]   [published]
    Signal Reconstruction from Multiple Unregistered Sets of Samples using Groebner Bases    
    IEEE Conference on Acoustics, Speech and Signal Processing; Toulouse, France, vol. 3, p. 604-607
    We present a new method for signal reconstruction from multiple sets of samples with unknown offsets. We rewrite the reconstruction problem as a set of polynomial equations in the unknown signal parameters and the offsets between the sets of samples. Then, we construct a Groebner basis for the corresponding affine variety. The signal parameters can then easily be derived from this Groebner basis. This provides us with an elegant solution method for the initial nonlinear problem. We show two examples for the reconstruction of polynomial signals and Fourier series.
    
    
61. Roy, Olivier; Vetterli, Martin   [RoyV:06b]   [published]
    Distributed Compression in Acoustic Sensor Networks Using Oversampled A/D Conversion    
    IEEE International Conference on Acoustic, Speech and Signal Processing (ICASSP); Toulouse, France, May 14-19, 2006, vol. 4, p. 165-168
    We address the problem of distributed compression in acoustic sensor networks. A typical scenario consists of a set of microphones that record a sound source located at some unknown position. The goal then is to convey the corresponding audio signals to a central base station for processing. We thus aim at designing efficient distributed communication schemes that minimize the overall bit-rate needed in order to achieve a given reconstruction accuracy. In this paper, we show how the a priori knowledge of the system's geometry can be beneficially used in order to lower the transmission rates. We propose a distributed coding scheme for simple synthetic sources. These results are then applied to more general signals by means of oversampled analog-to-digital conversion. Simulation results confirm the effectiveness of our approach. [pdf]
    
    
62. Konsbruck, Robert; Telatar, Emre; Vetterli, Martin   [KonsbruckTV:06]   [published]
    On the multiterminal rate-distortion function for acoustic sensing    
    IEEE Conference on Acoustics, Speech and Signal Processing, vol. 4, p. 701-704
    
    
    
63. Jovanovic, Ivana; Sbaiz, Luciano; Vetterli, Martin   [JovanovicSV:06]   [published]
    Acoustic Tomography Method for Measuring Temperature and Wind Velocity    
    IEEE International Conference on Acoustics, Speech, and Signal Processing; Toulouse, France, May 14-19, vol. 4, p. 1141-1144
    We consider the problem of reconstructing superimposed temperature and wind flow fields from acoustic measurements. A new technique based solely on acoustic waves propagation is presented. In contrast to the usual straight ray assumption, a bent ray model is considered in order to achieve higher accuracy. Under this assumption, we propose an iterative reconstruction algorithm that allows to entirely recover the considered fields. It alternates between estimating the fields of interest and the corresponding acoustic ray trajectories. Simulation results confirm the effectiveness and fast convergence of our scheme. [pdf]
    
    
64. Ajdler, Thibaut; Sbaiz, Luciano; Ridolfi, Andrea; Vetterli, Martin   [AjdlerSV:06]   [published]
    On a stochastic version of the plenacoustic function    
    IEEE Conference on Acoustics, Speech and Signal Processing; Toulouse, France, vol. 4, p. 1125-1128
    
    
    
65. Roy, Olivier; Vetterli, Martin   [RoyV:06]   [published]
    Collaborating Hearing Aids    
    MSRI Workshop on Mathematics of Relaying and Cooperation in Communication Networks; Berkeley, CA, USA, April 10-12, 2006
    Hearing aids are electronic, battery-operated sensing devices which aim at compensating various kinds of hearing impairments by means of appropriate signal processing. Most of today's hearing aid systems consist of two appliances working independently of each other. However, collaboration using a wireless communication link would allow to improve the overall beamforming capability of the system, hence providing better rejection of interfering signals. In this paper, the problem is considered from an information-theoretic viewpoint. We provide the necessary theoretical background to precisely quantify the gain achieved by collaboration as a function of the communication bit-rate. The beamforming capability is then discussed for the setup considered in this work. [pdf]
    
    
66. Vandewalle, Patrick; Süsstrunk, Sabine; Vetterli, Martin   [VandewalleSV:06]   [published]
    A Frequency Domain Approach to Registration of Aliased Images with Application to Super-Resolution    
    EURASIP Journal on Applied Signal Processing (special issue on Super-resolution), vol. 2006, p. Article ID 71459, 14 pages
    Super-resolution algorithms reconstruct a high resolution image from a set of low resolution images of a scene. Precise alignment of the input images is an essential part of such algorithms. If the low resolution images are undersampled and have aliasing artifacts, the performance of standard registration algorithms decreases. We propose a frequency domain technique to precisely register a set of aliased images, based on their low-frequency, aliasing-free part. A high resolution image is then reconstructed using cubic interpolation. Our algorithm is compared to other algorithms in simulations and practical experiments using real aliased images. Both show very good visual results and prove the attractivity of our approach in the case of aliased input images. A possible application is to digital cameras where a set of rapidly acquired images can be used to recover a higher resolution final image. [pdf]
    
    
67. Cristescu, Razvan; Beferull-Lozano, Baltasar; Vetterli, Martin; Wattenhofer, R.   [CristescuBVW:06]   [published]
    Network Correlated Data Gathering with Explicit Communication: NP-Completeness and Algorithms    
    IEEE/ACM Trans. on Networking, vol. 14, no 1, p. 41-54
    
    
    
68. Vandewalle, Patrick; Sbaiz, Luciano; Süsstrunk, Sabine; Vetterli, Martin   [VandewalleSSV:06]   [published]
    Registration of Aliased Images for Super-Resolution Imaging    
    SPIE/IS&T Visual Communications and Image Processing Conference; San Jose, CA, 15-19 January 2006, vol. 6077, p. 13-23
    Super-resolution imaging techniques reconstruct a high resolution image from a set of low resolution images that are taken from almost the same point of view. The problem can be subdivided into two main parts: an image registration part where the different input images are aligned with each other, and a reconstruction part, where the high resolution image is reconstructed from the aligned images. In this paper, we mainly consider the first step: image registration. We present three frequency domain methods to accurately align a set of undersampled images. First, we describe a registration method for images that have an aliasing-free part in their spectrum. The images are then registered using that aliasing-free part. Next, we present two subspace methods to register completely aliased images. Arbitrary undersampling factors are possible with these methods, but they have an increased computational complexity. In all three methods, we only consider planar shifts. We also show the results of these three algorithms in simulations and practical experiments. [pdf]
    
    
69. Barrenetxea, Guillermo; Vetterli, Martin; Beferull-Lozano, Baltasar   [Barrenetxea:06]   [published]
    Distributed routing algorithms for sensor networks    
    PhD thesis EPFL, accepted in Jan 2006 (Prof. M. Vetterli)
    Recent advances in wireless communications and computing technology are enabling the emergence of low-cost devices that incorporate sensing, processing, and communication functionalities. A large number of these devices are deployed in the field to create a sensor network for both monitoring and control purposes. Sensor networks are currently an active research area mainly due to the potential of their applications. However, the deployment of a working large scale sensor network still requires solutions to a number of technical challenges that stem primarily from the constraints imposed by simple sensor devices: limited power, limited communication bandwidth, and small storage capacity. In view of all these particular constraints, we require a new paradigm for communication, which consists of new algorithms specifically conceived for sensor networks. This thesis concentrates on the routing problem, that is, moving data among different network locations, and on the interactions between routing and coding, that is, how sensors code the observations. We start by designing efficient and computationally simple decentralized algorithms to transmit data from one single source to one single destination. We formalize the corresponding routing problem as a problem of constructing suitably constrained random walks on random graphs and derive distributed algorithms to compute the local parameters of the random walk that induces a uniform load distribution in the network. The main feature of this routing formulation is that it is possible to route messages along all possible routes between the source and the destination node, without performing explicit route discovery/repair computations and without maintaining explicit state information about available routes at the nodes. A natural extension to the single-source/single-destination scenario is to consider multiple sources and/or multiple destinations. Depending on the structure and goal of the network, nodes exhibit different communication patterns. We analyze the problem of routing under three different communication models, namely uniform communication, central data gathering, and border data gathering. For each of these models, we derive capacity limits and propose constructive routing strategies that achieve this capacity. An important constraint of sensor networks is the limited storage capacity available at the nodes. We analyze the problem of routing in networks with small buffers. We develop new approximation models to compute the distribution on the queue size at the nodes which provide a more accurate distribution than the usual Jackson's Theorem. Using these models, we design routing algorithms that minimize buffer overflow losses. Routing in large and unreliable networks, such as sensor networks, becomes prohibitively complex in terms of both computation and communication: due to temporary node failures, the set of available routes between any two nodes changes randomly. We demonstrate that achieving robust communications and maximizing the achievable rate per node are incompatible goals: while robust communications require the use of as many paths as possible between the source and the destination, maximizing the rate per node requires using only a few of the available paths. We propose a family of routing algorithms that explores this trade-off, depending on the degree of reliability of the network. The performance of routing algorithms in sensor networks can be significantly improved by considering the interaction of the source coding mechanism with the transport mechanism. We jointly optimize both the source coding and the routing algorithm in a common scenario encountered in sensor network, namely, real-time data transmission. We demonstrate that the combination of specially designed coding techniques, such as multiple description coding, and multipath routing algorithms, performs significantly better that the usual routing and coding schemes. In summary, this thesis revisits the classic routing problem in the light of distributed schemes for networks with resource-limited nodes. [pdf]
    
    
70. Cristescu, Razvan; Beferull-Lozano, Baltasar; Vetterli, Martin   [CristescuBV:05d]   [published]
    Networked Slepian-Wolf: Theory, Algorithms and Scaling Laws    
    IEEE Transactions on Information Theory, vol. 51, no 12, p. 4057-4073
    Consider a set of correlated sources located at the nodes of a network, and a set of sinks that are the destinations for some of the sources. The minimization of cost functions which are the product of a function of the rate and a function of the path weight is considered, for both the data-gathering scenario, which is relevant in sensor networks, and general traffic matrices, relevant for general networks. The minimization is achieved by jointly optimizing a) the transmission structure, which is shown to consist in general of a superposition of trees, and b) the rate allocation across the source nodes, which is done by Slepian-Wolf coding. The overall minimization can be achieved in two concatenated steps. First, the optimal transmission structure is found, which in general amounts to finding a Steiner tree, and second, the optimal rate allocation is obtained by solving an optimization problem with cost weights determined by the given optimal transmission structure, and with linear constraints given by the Slepian-Wolf rate region. For the case of data gathering, the optimal transmission structure is fully characterized and a closed-form solution for the optimal rate allocation is provided. For the general case of an arbitrary traffic matrix, the problem of finding the optimal transmission structure is NP-complete. For large networks, in some simplified scenarios, the total costs associated with Slepian-Wolf coding and explicit communication (conditional encoding based on explicitly communicated side information) are compared. Finally, the design of decentralized algorithms for the optimal rate allocation is analyzed.
    
    
71. Dubois-Ferrière, Henri; Estrin, Deborah; Vetterli, Martin   [Dubois-FerriereEV:05]   [published]
    Packet Combining in Sensor Networks    
    3rd ACM Conference on Embedded Networked Sensor Systems (SenSys 2005); San Diego, Nov. 2-4, 2005
    This paper presents the Simple Packet Combining (SPaC) error-correction scheme for wireless sensor networks. Nodes buffer corrupt packets, and when two or more corrupt versions of a packet have been received, a packet combining procedure attempts to recover the original packet from the corrupt copies. Packet combining exploits the broadcast medium and spatial diversity of a multi-hop wireless network by using packets overheard at any node, in addition to the next-hop destination of the packet itself. Unlike point-to-point forward error correction (FEC), packet combining therefore helps multi-node interactions such as multi-hop routing or broadcasting as well as to hop-by-hop communication. Also, SPaC does not transmit redundant overhead on good links and does not require costly probes to estimate channel conditions. We have implemented SPaC as a link-layer extension on sensor nodes; it is transparent to upper layer protocols and has low memory and CPU footprints. We evaluate performance through a combination of analysis, trace-driven simulation, indoor and outdoor testbed micro-benchmarks, and deployment on a live network. The results show significant performance gains, even when accounting for the energy cost of CPU processing. We also present detailed bit-level link measurements and the design and evaluation of a new preamble detection scheme motivated by these measurements.
    
    
72. Roy, Olivier; Vetterli, Martin   [RoyV:05]   [published]
    On the Asymptotic Distortion Behavior of the Distributed Karhunen-Loève Transform    
    Allerton Conference on Communication, Control and Computing; Monticello, IL, USA, September 28-30, 2005, p. 406-415
    The ability to design efficient distributed communications systems heavily depends on a proper understanding of the distortion incurred by their constituting elements. To this end, we study the mean squared reconstruction error behavior of the distributed Karhunen-Lo\`{e}ve transform. We provide a general formula to compute this distortion under asymptotic considerations in a pure approximation viewpoint. Using a simple illustrative example, we show how this approach allows to obtain closed-form formulas that permit to efficiently assess the performance of the distributed scheme. [pdf]
    
    
73. Vandewalle, Patrick; Sbaiz, Luciano; Vetterli, Martin; Süsstrunk, Sabine   [VandewalleSVS:05]   [published]
    Super-Resolution from Highly Undersampled Images    
    IEEE International Conference on Image Processing; Genova, Italy, September 2005, vol. 1, p. 889-892
    Aliasing artifacts in images are visually very disturbing. Therefore, most imaging devices apply a low-pass filter before sampling. This removes all aliasing from the image, but it also creates a blurred image. Actually, all the image information above half the sampling frequency is removed. In this paper, we present a new method for the reconstruction of a high resolution image from a set of highly undersampled and thus aliased images. We use the information in the entire frequency spectrum, including the aliased part, to create a sharp, high resolution image. The unknown relative shifts between the images are computed using a subspace projection approach. We show that the projection can be decomposed into multiple projections onto smaller subspaces. This allows for a considerable reduction of the overall computational complexity of the algorithm. A high resolution image can then be reconstructed from the registered low resolution images. Simulation results show the validity of our algorithm. [pdf]
    
    
74. Irena Maravic and Martin Vetterli   [MaravicV:05]   [published]
    Sampling and Reconstruction Methods for Signals of Finite Rate of Innovation in the Presence of Noise    
    IEEE Transactions on Signal Processing, Volume 53, Issue 8, Part 1, Aug 05
    Recently, it was shown that it is possible to develop exact sampling schemes for a large class of parametric non-bandlimited signals, namely, certain signals of finite rate of innovation \cite{Vetterli}. A common feature of such signals is that they have a finite number of degrees of freedom per unit of time and can be reconstructed from a finite number of uniform samples. In order to prove sampling theorems, Vetterli et al. considered the case of deterministic, noiseless signals, and developed algebraic methods that lead to perfect reconstruction. However, when noise is present, many of those schemes can become ill-conditioned. In this paper, we revisit the problem of sampling and reconstruction of signals with finite innovation rate and propose improved, more robust methods that have better numerical conditioning in the presence of noise and yield more accurate reconstruction. We analyze in detail a signal made up of a stream of Diracs and develop algorithmic tools that will be used as a basis in all constructions. While some of the techniques have been already encountered in the spectral estimation framework, we further explore preconditioning methods that lead to improved resolution performance in the case when the signal contains closely spaced components. For classes of periodic signals, such as piecewise polynomials and nonuniform splines, we propose novel algebraic approaches that solve the sampling problem in the Laplace domain, after appropriate windowing. Building up on the results for periodic signals, we extend our analysis to finite-length signals and develop schemes based on a Gaussian kernel, which avoid the problem of ill-conditioning by proper weighting of the data matrix. Our methods use structured linear systems and robust algorithmic solutions, which we show through simulation results. [pdf]
    
    
75. Ajdler, Thibaut; Faller, Christof; Sbaiz, Luciano; Vetterli, Martin   [AjdlerFSV:05]   [published]
    Head Related Transfer Functions Interpolation Considering Acoustics    
    118th Audio Engineering Society Convention; Barcelona, Spain
    
    
    
76. R. Cristescu and M. Vetterli   [CristescuV:05]   [published]
    On the Optimal Density for Real-Time Data Gathering of Spatio-Temporal Processes in Sensor Networks    
    4th International Conference on Information Processing in Sensor Networks (IPSN'05), UCLA, 25-27 Apr 05
    
    
    
77. Ajdler, Thibaut; Sbaiz, Luciano; Vetterli, Martin   [AjdlerSV:05]   [published]
    The plenacoustic function on the circle with application to HRTF interpolation    
    IEEE Conference on Acoustics, Speech and Signal Processing, vol. 3, p. 273 - 276
    
    
    
78. R. Cristescu, B. Beferull-Lozano, M. Vetterli, D. Ganesan and J. Acimovic   [CristescuBVG:05]   [published]
    On the Interaction of Data Representation and Routing in Sensor Networks    
    IEEE Conference on Acoustics, Speech and Signal Processing (ICASSP2005), Philadelphia, 18-23 Mar 05
    
    
    
79. Gastpar, Michael; Vetterli, Martin   [GastparV:05]   [published]
    On the Capacity of Large Gaussian Relay Networks    
    IEEE Transactions on Information Theory, vol. 51, no 3, p. 765-779
    The capacity of a particular large Gaussian relay network is determined in the limit as the number of relays tends to infinity. Upper bounds are derived from cut-set arguments, and lower bounds follow from an argument involving uncoded transmission. It is shown that in cases of interest, upper and lower bounds coincide in the limit as the number of relays tends to infinity. Hence, this paper provides a new example where a simple cut-set upper bound is achievable, and one more example where uncoded transmission achieves optimal performance. The findings are illustrated by geometric interpretations. The techniques developed in this paper are then applied to a sensor network situation. This is a network joint source–channel coding problem, and it is well known that the source–channel separation theorem does not extend to this case. The present paper extends this insight by providing an example where separating source from channel coding does not only lead to suboptimal performance, it leads to an exponential penalty in performance scaling behavior (as a function of the number of nodes). Finally, the techniques developed in this paper are extended to include certain models of ad hoc wireless networks, where a capacity scaling law can be established: When all nodes act purely as relays for a single source–destination pair, capacity grows with the logarithm of the number of nodes. [pdf]
    
    
80. Cristescu, Razvan; Beferull-Lozano, Baltasar; Vetterli, Martin   [CristescuBV:04c]   [published]
    Scaling Laws for Correlated Data Gathering    
    IEEE International Symposium on Information Theory (ISIT), p. 472
    Consider a set of correlated sources located at the nodes of a network, and a sink to which the data from all the sources has to arrive. We address the minimization of a separable joint communication cost function given by the product [rate] $\times$ [edge weight]. We consider the data gathering scenario, which is relevant in sensor networks. We present two possible approaches for rate allocation, namely Slepian-Wolf coding, and coding by explicit communication. We compare asymptotically (dense networks) the total costs associated with Slepian-Wolf coding and explicit communication, by finding their corresponding scaling laws and analyzing the ratio of their respective costs. We also provide the specific conditions on the correlation structure which determine the different cases of asymptotic behaviors.
    
    
81. Maravic, Irena; Vetterli, Martin; Ramchandran, Kannan   [MaravicVR:04]   [published]
    Channel Estimation and Synchronization with Sub-Nyquist Sampling and Application to Ultra-Wideband Systems    
    Proceedings IEEE International Symposium on Circuits and Systems, vol. 5, p. 381-384
    We consider the problem of low-complexity channel estimation and timing in digital ultra-wideband receivers. We extend some of our recent results on sampling of certain classes of parametric non-bandlimited signals and develop a frequency domain framework that yields high-resolution estimates of all relevant channel parameters by sampling a received signal below the traditional Nyquist rate. In particular, we show that the minimum required sampling rate in an UWB receiver is determined by the so-called {\em innovation rate}, which corresponds to the number of degrees of freedom of the received UWB signal. Our framework allows for faster acquisition compared to current digital solutions and potentially reduces power consumption and complexity of digital UWB receivers significantly. It is particularly suitable in applications such as ranging or positioning and can also be used for identification of more realistic UWB channel models, where different propagation paths undergo different frequency-selective mitigation. [pdf]
    
    
82. Vandewalle, Patrick; Sbaiz, Luciano; Vandewalle, Joos; Vetterli, Martin   [VandewalleSVV:04]   [published]
    How to take advantage of aliasing in bandlimited signals    
    IEEE Conference on Acoustics, Speech and Signal Processing, vol. 3, p. 948-951
    In signal processing systems, aliasing is normally treated as a disturbing signal. That motivates the need for effective analog, optical and digital anti-aliasing filters. However, aliasing conveys also valuable information on the signal above the Nyquist frequency. Hence, an effective processing of the samples, based on a model of the input signal, would allow to virtually increase the sampling frequency using slower and cheaper converters. In this paper, we present such an algorithm for bandlimited signals that are sampled below twice the maximum signal frequency. Using a subspace method in the frequency domain, we show that these signals can be reconstructed from multiple sets of samples. The offset between the sets is unknown and can have arbitrary values. This approach can be applied to the creation of super-resolution images from sets of low resolution images. In this application, registration parameters have to be computed from aliased images. We show that parameters and high resolution images can be computed precisely, even when high levels of aliasing are present on the low resolution images. [pdf]
    
    
83. Gastpar, Michael; Dragotti, Pier Luigi; Vetterli, Martin   [GastparDV:04]   [published]
    On Compression Using the Distributed Karhunen-Loeve Transform    
    IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), vol. 3, p. 901-904
    In this paper, we discuss a framework for the distributed compression of vector sources, based on our previous work on distributed transform coding. In particular, our goal is to develop a strategy of first applying a suitable distributed Karhunen-Loeve transform, whereafter each component can be andled by standard distributed compression techniques. In the present paper, we first study the scenario where all but one terminal furnish a noisy approximation of their observation. For the case where the underlying vector is Gaussian, and the added noise is also Gaussian, we establish that indeed, it is optimal for the last terminal to apply a (local) transform to its observations, and to separately compress each component in the transform domain. Then, we outline how this leads to a general simple distributed compression strategy for Gaussian vector sources: Each terminal applies a suitable local transform to its observations, and encodes the resulting components separately in a Wyner-Ziv fashion, i.e., treating the compressed descriptions of all other terminals as side information available to the decoder. This achieves the best known performance. The optimum performance in unknown to date.
    
    
84. Baltasar Beferull-Lozano, Robert L. Konsbruck, Martin Vetterli   [BeferullKV:04b]   [published]
    Rate-Distortion Problem for Physics Based Distributed Sensing    
    IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP '04), Montreal, 17-21 May 2004.
    We consider the rate-distortion problem for sensing the continuous space-time physical temperature in a circular ring on which a heat source is applied over space and time, and which is allowed to cool by radiation or convection. The heat source is modelled as a continuous space-time stochastic process which is bandlimited over space and time. The temperature field is the result of a certain continuous space-time convolution of the heat source with the Green's function corresponding to the heat equation, which is space and time invariant. The temperature field is sampled at uniform spatial locations by a set of sensors and it has to be reconstructed at a base station. The goal is to minimize the mean-square-error per second, for a given number of nats per second, assuming ideal communication channels between sensors and base station. We find a) the centralized R^c(D) function of the temperature field, where the base station can optimally encode all the space-time samples jointly. Then, we obtain b) the R^{s-i}(D) function, where each sensor, independently, encodes its samples optimally over time and c) the R^{st-i}(D) function, where each sensor is constrained to encode also independently over time. We also study two distributed prediction-based approaches: a) with perfect feedback from the base station, where temporal prediction is performed at the base station and each sensor performs differential encoding, and b) without feedback, where each sensor locally performs temporal prediction. [pdf]
    
    
85. Baltasar Beferull-Lozano, Robert L. Konsbruck, Martin Vetterli   [BeferullKV:04a]   [published]
    Rate-Distortion Problem for Physics Based Distributed Sensing    
    3rd Symposium on Information Processing in Sensor Networks (IPSN '04), Berkeley, California, USA, 26-27 April 2004.
    We consider the rate-distortion problem for sensing the continuous space-time physical temperature in a circular ring on which a heat source is applied over space and time, and which is allowed to cool by radiation or convection. The heat source is modelled as a continuous space-time stochastic process which is bandlimited over space and time. The temperature field is the result of a certain continuous space-time convolution of the heat source with the Green's function corresponding to the heat equation, which is space and time invariant. The temperature field is sampled at uniform spatial locations by a set of sensors and it has to be reconstructed at a base station. The goal is to minimize the mean-square-error per second, for a given number of nats per second, assuming ideal communication channels between sensors and base station. We find a) the centralized R^c(D) function of the temperature field, where the base station can optimally encode all the space-time samples jointly. Then, we obtain b) the R^{s-i}(D) function, where each sensor, independently, encodes its samples optimally over time and c) the R^{st-i}(D) function, where each sensor is constrained to encode also independently over time. We also study two distributed prediction-based approaches: a) with perfect feedback from the base station, where temporal prediction is performed at the base station and each sensor performs differential encoding, and b) without feedback, where each sensor locally performs temporal prediction. [pdf]
    
    
86. Barrenetxea, Guillermo; Beferull-Lozano, Baltasar; Vetterli, Martin   [BarrenecheaBV:04a]   [published]
    Lattice Sensor Networks: Capacity Limits, Optimal Routing and Robustness to Failures    
    Information Processing in Sensor Networks (IPSN'04), p. 186-195
    We study network capacity limits and optimal routing algorithms for regular sensor networks, namely, square and torus grid sensor networks, in both, the static case (no node failures) and the dynamic case (node failures). For static networks, we derive upper bounds on the network capacity and then we characterize and provide optimal routing algorithms whose rate per node is equal to this upper bound, thus, obtaining the exact analytical expression for the network capacity. We also provide the scaling law for the required size of the node buffer as a function of the network size. For dynamic networks, the unreliability of the network is modeled in two ways: a Markovian node failure and an energy based node failure. Depending on the probability of node failure that is present in the network, we propose to use a particular combination of two routing algorithms, the first one being optimal when there are no node failures at all and the second one being optimal when the probability of node failure is sufficiently high. The combination of these two routing algorithms defines a family of randomized routing algorithms, each of them being appropriate for a given probability of node failure.
    
    
87. Gastpar, Michael; Vetterli, Martin   [GastparV:04]   [published]
    Power-bandwidth-distortion scaling laws for sensor networks    
    Third International Symposium on Information Processing in Sensor Networks (IPSN), p. 320-329
    
    
    
88. Cristescu, Razvan; Vetterli, Martin   [Cristescu:04]   [published]
    Efficient decentralized communications in sensor networks    
    PhD Thesis EPFL , accepted in Mar 2004, Prof. M. Vetterli
    In the first part of this thesis, we consider the problem of correlated data gathering by a network with a sink node and a tree communication structure, where the goal is to minimize the total transmission cost of transporting the information collected by the nodes, to the sink node. Two coding strategies are analyzed: a Slepian-Wolf model where optimal coding is complex and transmission optimization is simple, and a joint entropy coding model with explicit communication where coding is simple and transmission optimization is difficult. This problem requires a joint optimization of the rate allocation at the nodes and of the transmission structure. For the Slepian-Wolf setting, we derive a closed form solution and an efficient distributed approximation algorithm with a good performance. We generalize our results to the case of multiple sinks. For the explicit communication case, we prove that building an optimal data gathering tree is NP-complete and we propose various distributed approximation algorithms. We compare asymptotically, for dense networks, the total costs associated with Slepian-Wolf coding and explicit communication, by finding their corresponding scaling laws and analyzing the ratio of their respective costs. We argue that, for large networks and under certain conditions on the correlation structure, 'intelligent', but more complex Slepian-Wolf coding provides unbounded gains over the widely used straightforward approach of opportunistic aggregation and compression by explicit communication. In the second part of this thesis, we consider a queuing problem in which the service rate of a queue is a function of a partially observed Markov chain, and in which the arrivals are controlled based on those partial observations so as to keep the system in a desirable mildly unstable regime. The optimal controller for this problem satisfies a separation property: we first compute a probability measure on the state space of the chain, namely the information state, then use this measure as the new state based on which to make control decisions. We give a formal description of the system considered and of its dynamics, we formalize and solve an optimal control problem, and we show numerical simulations to illustrate with concrete examples properties of the optimal control law. We show how the ergodic behavior of our queuing model is characterized by an invariant measure over all possible information states, and we construct that measure. Our results may be applied for designing efficient and stable algorithms for medium access control in multiple accessed systems, in particular for sensor networks.
    
    
89. Cristescu, Razvan; Beferull-Lozano, Baltasar; Vetterli, Martin   [CristescuBV:04b]   [published]
    On Network Correlated Data Gathering    
    INFOCOM, vol. 4, p. 2571-2582
    We consider the problem of correlated data gathering by a network with a sink node and a tree communication structure, where the goal is to minimize the total transmission cost of transporting the information collected by the nodes, to the sink node. Two coding strategies are analyzed: a Slepian-Wolf model where optimal coding is complex and transmission optimization is simple, and a joint entropy coding model with explicit communication where coding is simple and transmission optimization is difficult. This problem requires a joint optimization of the rate allocation at the nodes and of the transmission structure. For the Slepian-Wolf setting, we derive a closed form solution and an efficient distributed approximation algorithm with a good performance. For the explicit communication case, we prove that building an optimal data gathering tree is NP-complete and we propose various distributed approximation algorithms. [pdf]
    
    
90. Vandewalle, Patrick; Süsstrunk, Sabine; Vetterli, Martin   [VandewalleSV:04]   [published]
    Double resolution from a set of aliased images    
    Proc. IS&T/SPIE Electronic Imaging 2004: Sensors and Camera Systems for Scientific, Industrial, and Digital Photography Applications V, vol. 5301, p. 374-382
    In this paper, we present a super-resolution method to approximately double image resolution in both dimensions from a set of four low resolution, aliased images. The camera is shifted and rotated by small amounts between the different image captures. Only the low frequency, aliasing-free part of the images is used to find the shift and rotation parameters. When the images are registered, it is possible to reconstruct a higher resolution, aliasing-free image from the four low resolution images using cubic interpolation. We applied our algorithm in a simulation, where all parameters are known and controlled, as well as in a practical experiment using images taken with a real digital camera. The results obtained in both tests prove the validity of our method. [pdf]
    
    
91. Cristescu, Razvan; Beferull-Lozano, Baltasar; Vetterli, Martin   [CristescuBV:04a]   [published]
    Networked Slepian-Wolf: Theory and Algorithms    
    EWSN, p. 44-59
    In this paper, we consider the minimization of a relevant energy consumption related cost function in the context of sensor networks where correlated sources are generated at various sets of source nodes and have to be transmitted to some set of sink nodes. The cost function we consider is given by the product [rate] $\times$ [link weight]. The minimization is achieved by jointly optimizing the transmission structure, which we show consists of a superposition of trees from each of the source nodes to its corresponding sink nodes, and the rate allocation across the source nodes. We show that the overall minimization can be achieved in two concatenated steps. First, the optimal transmission structure has to be found, which in general amounts to finding a Steiner tree and second, the optimal rate allocation has to be obtained by solving a linear programming problem with linear cost weights determined by the given optimal transmission structure. We also prove that, if any arbitrary traffic matrix is allowed, then the problem of finding the optimal transmission structure is NP-complete. For some particular traffic matrix cases, we fully characterize the optimal transmission structures and we also provide a closed-form solution for the optimal rate-allocation. Finally, we analyze the design of decentralized algorithms in order to obtain exactly or approximately the optimal rate allocation, depending on the traffic matrix case. For the particular case of data gathering, we provide experimental results showing a good performance in terms of approximation ratios.
    
    
92. Maravic, Irena; Vetterli, Martin   [MaravicV:04a]   [published]
    Exact Sampling Results for Some Classes of Parametric Non-Bandlimited 2-D Signals    
    IEEE Transactions on Signal Processing, vol. 52, no 1, p. 175-189
    We present sampling results for certain classes of two-dimensional signals that are not bandlimited, but have a parametric representation with a finite number of degrees of freedom. While there are many such parametric signals, it is often difficult to propose practical sampling schemes, therefore, we will concentrate on those classes for which we are able to give exact sampling algorithms and reconstruction formulas. We analyze in detail a set of 2-D Diracs and extend the results to more complex objects such as lines and polygons. Unlike most multidimensional sampling schemes, the methods we propose perfectly reconstruct such signals from a finite number of samples. Some of the techniques we use are already encountered in the context of harmonic retrieval and error correction coding. In particular, singular value decomposition based methods and the annihilating filter approach are both explored as inherent parts of the proposed algorithms. Applications of our results can be found in astronomical signal processing, image processing and in some classes of identification problems. [pdf]
    
    
93. Maravic, Irena; Kusuma, Julius; Vetterli, Martin   [MaravicKV:03]   [published]
    Low-Sampling Rate UWB Channel Characterization and Synchronization    
    Journal of Communications and Networks KOR, special issue on ultra-wideband systems, vol. 5, no 4, p. 319-327
    We consider the problem of low-sampling rate high-resolution channel estimation and timing for digital ultra-wideband (UWB) receivers. We extend some of our recent results in sampling of certain classes of parametric non-bandlimited signals and develop a frequency domain method for channel estimation and synchronization in ultra-wideband systems, which uses sub-Nyquist uniform sampling and well-studied computational procedures. In particular, the proposed method can be used for identification of more realistic channel models, where different propagation paths undergo different frequency-selective fading. Moreover, we show that it is possible to obtain high-resolution estimates of all relevant channel parameters by sampling a received signal below the traditional Nyquist rate. Our approach leads to faster acquisition compared to current digital solutions, allows for slower A/D converters, and potentially reduces power consumption of digital UWB receivers significantly. [pdf]
    
    
94. Dubois-Ferrière, Henri; Grossglauser, Matthias; Vetterli, Martin   [Dubois-FerriereGV:03b]   [published]
    Space-Time Routing in Ad Hoc Networks    
    Proc. 2nd International Conference on AD-HOC Networks and Wireless (also app. in Lecture Notes in Computer Science, Nr. 2865)
    [pdf]
    
    
95. Vandewalle, Patrick; Süsstrunk, Sabine; Vetterli, Martin   [VandewalleSV:03]   [published]
    Superresolution images reconstructed from aliased images    
    Proc. SPIE/IS&T Visual Communications and Image Processing Conference, vol. 5150, p. 1398-1405
    In this paper, we present a simple method to almost quadruple the spatial resolution of aliased images. From a set of four low resolution, undersampled and shifted images, a new image is constructed with almost twice the resolution in each dimension. The resulting image is aliasing-free. A small aliasing-free part of the frequency domain of the images is used to compute the exact subpixel shifts. When the relative image positions are known, a higher resolution image can be constructed using the Papoulis-Gerchberg algorithm. The proposed method is tested in a simulation where all simulation parameters are well controlled, and where the resulting image can be compared with its original. The algorithm is also applied to real, noisy images from a digital camera. Both experiments show very good results. [pdf]
    
    
96. Ajdler, Thibaut; Vetterli, Martin   [AjdlerV:03b]   [published]
    Acoustic Based Rendering by Interpolation of the Plenacoustic Function    
    SPIE/IS&T Visual Communications and Image Processing Conference, vol. 5150, p. 1337-1346
    We study the spatialization of the sound field in a room, in particular the evolution of room impulse responses as function of their spatial positions. The presented technique allows us to completely characterize the sound field in any arbitrary location if the sound field is known in a certain finite number of positions. In this paper, we include an analytical solution of the problem for any rectangular room. Further results on reconstruction of the sound field by interpolation of the Plenacoustic function are discussed.
    
    
97. Maravic, Irena; Vetterli, Martin   [MaravicV:03a]   [published]
    Low-Complexity Subspace Methods for Channel Estimation and Synchronization in Ultra-Wideband Systems    
    Proc. International Workshop on Ultra-Wideband Systems (IWUWB)
    We consider the problem of low-complexity channel estimation in digital ultra-wideband receivers. We extend some of our recent sampling results for certain classes of parametric non-bandlimited signals and develop several methods that take advantage of transform techniques to estimate channel parameters from a low-dimensional subspace of a received signal, that is, by sampling the signal below the Nyquist rate. By lowering the sampling rate we reduce computational requirements compared to current digital solutions, allow for slower A/D converters and potentially significantly reduce power consumption of digital receivers. Our approach is particularly suitable for indoor wireless sensor networks, where low rates and low power consumption are required. One application of our framework to high-resolution acquisition in ultra-wideband localizers is also presented.
    
    
98. Dubois-Ferrière, Henri; Grossglauser, Matthias; Vetterli, Martin   [Dubois-FerriereGV:03]   [published]
    Age Matters: Efficient Route Discovery in Mobile Ad Hoc Networks Using Encounter Ages    
    Proc ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHOC), p. 257-266
    We propose FResher Encounter SearcH (FRESH), a simple algorithm for efficient route discovery in mobile ad hoc networks. Nodes keep a record of their most recent encounter times with all other nodes. Instead of searching for the destination, the source node searches for any intermediate node that encountered the destination {\em more recently than did the source node itself}. The intermediate node then searches for a node that encountered the destination yet more recently, and the procedure iterates until the destination is reached. Therefore, FRESH replaces the single network-wide search of current proposals with a succession of smaller searches, resulting in a cheaper route discovery. Routes obtained are loop-free. The performance of such a scheme will depend on the nodes' mobility processes. Under standard mobility processes our simulations show that route discovery cost can be decreased by an order of magnitude, a significant gain given that route discovery is a major source of routing overhead in ad hoc networks. [ps]
    
    
99. Cristescu, Razvan; Vetterli, Martin   [CristescuV:03]   [published]
    Power Efficient Gathering of Correlated Data: Optimization, NP-Completeness and Heuristics    
    Proc. MobiHoc, vol. 7, no 3, p. 31-32
    This paper studies the interaction between the communication costs in a sensor network and the structure of the data that it measures. We formulate an optimization problem definition for power efficient data gathering and assess its computational difficulty. In particular, we show that the problem is NP-complete. We propose some scalable, distributed and efficient heuristic algorithms for solving this problem and show by numerical simulations that the power consumption can be significantly improved over direct transmission or the shortest path tree, with up to 40% for highly correlated data. Also, our algorithms provide solutions close to a computationally heavy heuristic which we use as benchmark, simulated annealing, which is provably optimal in the limit.
    
    
100. Gastpar, Michael; Rimoldi, Bixio; Vetterli, Martin   [GastparRV:03]   [published]
     To code or not to code: lossy source-channel communication revisited    
     IEEE Transactions on Information Theory, vol. 49, no 5, p. 1147-1158
     
     
     
101. Kusuma, Julius; Maravic, Irena; Vetterli, Martin   [KusumaMV:02]   [published]
     Sampling With Finite Rate of Innovation: Channel and Timing Estimation for UWB and GPS    
     IEEE International Conference on Communications (ICC); Anchorage, Alaska, 11-15 May 2003, vol. 5, p. 3540-3544
     Abstract—In this work, we consider the problem of channel estimation by using the recently developed theory for sampling of signals with a finite rate of innovation [1]. We show a framework which allows for lower than Nyquist rate sampling applicable for timing and channel estimation of both narrowband and wideband channels. In certain cases we demonstrate performance exceeding that of algorithms using Nyquist rate sampling while working at lower sampling rates, thus saving power and computational complexity. [pdf]
     
     
102. G. Barrenechea, B. Beferull-Lozano, A. Verma, P.L. Dragotti, M. Vetterli   [BarrenecheaBVDV:03]   [published]
     Multiple Description Source Coding and Diversity Routing: A Joint Source Approach to Real-Time Services over Dense Networks    
     13th International Packet Video Workshop, Nantes, 28-29 April 2003
     We investigate the interaction of the source coding mechanism and the transport mechanism for real time data packet transmission over dense networks. We show that single path routing does not make efficient use of network capacity whereas multi path routing techniques do (Proposition 1 and 2). We then consider the interaction of single versus multiple description source coding with single versus multi path routing. The most sophisticated scheme (multiple descriptions source coding and multi path routing) performs significantly better that the usual single path and single description scheme. This improvement is more remarkable in the case of low rates and shorter maximum allowed delay (about 18 dB in the best case). This scheme is more robust over a wide range of network behavior, thus indicating the benefit of such methods in large networks where links and nodes are subject to failures.
     
     
103. Ajdler, Thibaut; Vetterli, Martin   [AjdlerV:03]   [published]
     The Plenacoustic Function, Sampling and Reconstruction    
     IEEE Conference on Acoustics, Speech and Signal Processing, vol. 5, p. 616-619
     In the present paper, we study the spatialization of the soundfield in a room, in particular the evolution of room impulse responses as function of their spatial positions. The presented technique allows us to completely characterize the sound field in any arbitrary location if the sound field is known in a certain finite number of positions. The existing techniques make usually use of room models to recreate the sound field present at some point in the space. Our technique simply starts from the measurements of impulse responses in a finite number of positions and with this information the total sound field can be recreated. An analytical solution of the problem is given for different cases of spaces. Further, we determine the number and the spacing between the microphones needed to perfectly reconstruct the sound field up to a certain temporal frequency. The optimal sampling pattern for the microphone positions is given. Applications are also discussed. [pdf]
     
     
104. T. Ajdler, R. Cristescu, P.L. Dragotti, M. Gastpar, I. Maravic, M. Vetterli   [AjdlerCDGMV:03]   [published]
     Distributed Signal Processing and Communications: on the Interaction of Sources and Channels, invited paper    
     IEEE ICASSP, Hong Kong, 6-10 April 2003
     Distributed ways of communicating, processing, and sensing are replacing more traditional centralized architectures. An early example of this revolution in distributed communications is appearing in the form of sensor networks, which are densely distributed networks of embedded signal sensors, controls and processors. These nodes could be simple signal sensors, but couldalso be cameras and microphones.In this distributed scenario, there are several interesting topics to investigate that span from traditional signal processing problems (i.e, sampling, compression, detection) tocommunication and information theory (i.e, transmission protocols, capacity bounds for ad-hoc networks). This paper reviews some recent results on the topic of source representations and distributed source coding and transmission. [ps]
     
     
105. Maravic, Irena; Vetterli, Martin; Ramchandran, Kannan   [MaravicVR:03]   [published]
     High-Resolution Acquisition Methods for Wideband Communication Systems    
     IEEE Conference on Acoustics, Speech and Signal Processing, vol. 4, p. 133-136
     We consider the problem of low-complexity timing synchronization in digital receivers for DS-CDMA and UWB systems operating over channels with single or multiple propagation paths. We extend some of our recent sampling results for certain classes of non-bandlimited signals and develop a method that takes advantage of transform techniques to perform propagation delay estimation from a low-dimensional subspace of a received signal, that is, by sampling below the Nyquist rate. By lowering the sampling rate we reduce computational requirements compared to existing solutions, allow for slower A/D converters and significantly reduce power consumption of digital receivers.
     
     
106. Grossglauser, Matthias; Vetterli, Martin   [GrossglauserV:03b]   [published]
     Locating nodes with EASE: last encounter routing for Ad Hoc networks through mobility diffusion    
     Proc. IEEE Infocom, vol. 3, p. 1954-1964
     
     
     
107. Hasler, David; Sbaiz, Luciano; Süsstrunk, Sabine; Vetterli, Martin   [HaslerSSV:03]   [published]
     Outlier modeling in image matching    
     IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 25, no 3, p. 301-315
     We address the question of how to characterize the outliers that may appear when matching two views of the same scene. The match is performed by comparing the difference of the two views at a pixel level, aiming at a better registration of the images. When using digital photographs as input, we notice that an outlier is often a region that has been occluded, an object that suddenly appears in one of the images, or a region that undergoes an unexpected motion. By assuming that the error in pixel intensity levels generated by the outlier is similar to an error generated by comparing two randomly picked regions in the scene, we can build a model for the outliers based on the content of two views. We illustrate our model by solving a pose estimation problem: the goal is to compute the camera motion between two views. The matching is expressed as a mixture of inliers versus outliers an defines a function to minimise for improving the pose estimation. Our model has two benefits: First it delivers a probability for each pixel to belong to the outliers. Second our tests show that the method is substantially more robust than traditional robust estimators (M-estimators) used in image stitching applications, with only a slightly higher computational complexity. [pdf]
     
     
108. Gastpar, Michael; Dragotti, Pier Luigi; Vetterli, Martin   [GastparDV:02]   [published]
     The distributed Karhunen-Loeve transform    
     IEEE International Workshop on Multimedia Signal Processing, p. 57-60
     The Karhunen-Loeve transform is a key element of many signal processing tasks, including classification and compression. In this paper, we consider distributed signal processing scenarios with limited communication between correlated sources, and we investigate a distributed Karhunen-Loeve transform (KLT). In particular, a partial KLT (where only a subset of sources are observed) and a conditional KLT (where some sources act as side information) are posed and solved in a rate-distortion sense. The partial KLT leads to an original bit allocation problem, while the conditional KLT leads to a Wyner Ziv solution which is separable at the sources. These two cases can be seen as extreme cases of a distributed KLT.
     
     
109. Ajdler, Thibaut; Vetterli, Martin   [AjdlerV:02]   [published]
     The Plenacoustic Function and its Sampling    
     Proc. IEEE Benelux Workshop on Model Based Processing and Coding of Audio (MPCA)
     In this paper, we study the spatialization of the sound field in rooms, in particular the evolution of the room impulse responses in function of their spatial positions. Thanks to this study, we are now able to predict the sound field in any position knowing the sound field in a certain number of positions in the room. If enough measurements are taken, we are able to completely characterize the sound field of the room at any arbitrary location. Further, we determine the number and the spacing between the microphones needed to reconstruct the sound field in a room up to a certain temporal frequency. [pdf]
     
     
110. Gastpar, Michael; Vetterli, Martin   [Gastpar:02]   [published]
     To code or not to code    
     PhD Thesis EPFL, accepted in Nov 2002 (Prof. M. Vetterli and B. Rimoldi( (best EPFL thesis)
     
     
     
111. Dragotti, Pier Luigi; Servetto, Sergio D.; Vetterli, Martin   [DragottiSV:02]   [published]
     Optimal Filter Banks for Multiple Description Coding: Analysis and Synthesis    
     IEEE Transactions on Information Theory, vol. 48, no 7, p. 2036-2052
     
     
     
112. Vetterli, Martin; Marziliano, Pina; Blu, Thierry   [VetterliMB:02]   [published]
     Sampling signals with finite rate of innovation    
     IEEE Transactions on Signal Processing, vol. 50, no 6, p. 1417-1428
     Consider classes of signals that have a finite number of degrees of freedom per unit of time and call this number the rate of innovation. Examples of signals with a finite rate of innovation include streams of Diracs (e.g., the Poisson process), nonuniform splines, and piecewise polynomials. Even though these signals are not bandlimited, we showthat they can be sampled uniformly at (or above) the rate of innovation using an appropriate kernel and then be perfectly reconstructed. Thus, we prove sampling theorems for classes of signals and kernels that generalize the classic "bandlimited and sinc kernel" case. In particular, we show how to sample and reconstruct periodic and finite-length streams of Diracs, nonuniform splines, and piecewise polynomials using sinc and Gaussian kernels. For infinite-length signals with finite local rate of innovation, we show local sampling and reconstruction based on spline kernels. The key in all constructions is to identify the innovative part of a signal (e.g., time instants and weights of Diracs) using an annihilating or locator filter: a device well known in spectral analysis and error-correction coding. This leads to standard computational procedures for solving the sampling problem, which we show through experimental results. Applications of these new sampling results can be found in signal processing, communications systems, and biological systems.
     
     
113. Gastpar, Michael; Vetterli, Martin   [GastparV:02]   [published]
     On the capacity of wireless networks: the relay case    
     Proc. IEEE Infocom, vol. 3, p. 1577-1586
     No abstract [ps]
     
     
114. Maravic, Irena; Vetterli, Martin   [MaravicV:02b]   [published]
     A sampling theorem for the radon transform of finite complexity objects    
     IEEE Conference on Acoustics, Speech and Signal Processing, vol. 2, p. 1197-1200
     See full text [pdf]
     
     
115. Kusuma, Julius; Ridolfi, Andrea; Vetterli, Martin   [KusumaRV:02]   [published]
     Sampling of communications systems with bandwidth expansion    
     Proc. IEEE ICC, vol. 3, p. 1601-1605
     Many communication systems are {\em bandwidth-expanding}: the transmitted signal occupies a bandwidth larger than the {\em symbol rate}. The sampling theorems of Kotelnikov, Shannon, Nyquist et al. shows that in order to represent a bandlimited signal, it is necessary to sample at what is popularly referred to as the Shannon or Nyquist rate. However, in many systems, the required sampling rate is very high and expensive to implement. In this work we show that it is possible to get suboptimal performance by sampling close to the {\em symbol rate} of the signal, using well-studied algorithmic components. This work is based on recent results on sampling for some classes of non-bandlimited signals. In the present paper, we extend these sampling results to the case when there is noise. In our exposition, we use Ultra Wideband (UWB) signals as an example of how our framework can be applied. [pdf]
     
     
116. Gastpar, Michael; Rimoldi, Bixio; Vetterli, Martin   [GastparRV:01]   [published]
     On source/channel codes of finite block length    
     IEEE International Symposium on Information Theory, p. 261
     For certain fortunate choices of source/channel pairs, all sophisticated coding is in vain: for them, a code of block length one is sufficient to achieve optimal performance \cite{mgbrmvtrans}. Is the set of ``fortunate choices'' larger if we allow for codes of block length $M$? For a certain class of discrete memoryless source/channel pairs, we can prove that the answer is negative as long as $M$ is finite. [ps]
     
     
117. Hubaux, Jean-Pierre; Gross, Thomas; Le Boudec, Jean-Yves; Vetterli, Martin   [HubauxGLV:01]   [published]
     Towards self-organized mobile ad hoc networks: The terminodes project    
     IEEE Communications Magazine, vol. 39, no 1, p. 118-124
     This article provides a technical overview of mobile ad hoc networks and describes their long-term potential. It covers current research, and describes major technical challenges, including networking, real-time services, and software. It shows that by their very nature, mobile ad hoc networks can bring a paradigm shift in the way networks are organized and operated, and can even lead to a fundamental change in the relationships between information technology and societal organization. As an illustration of these concepts, the article also contains an overall description of our long-term research project, called terminodes [pdf]
     
     
118. Gastpar, Michael; Rimoldi, Bixio; Vetterli, Martin   [GastparRV:00b]   [published]
     On optimal low-complexity source/channel coding    
     Winter School in Coding and Information Theory
     Shannon's separation theorem gives a conceptually and practically appealing way to construct an optimal communication system in two independent steps, namely source compression and channel coding. However, sometimes it is worth considering {\em joint} source/ channel coding instead. In fact, for certain source/channel pairs, not using any code at all already achieves the optimum performance. For a larger class ${\mathbb S}$ of source/channel pairs, there exists a single-letter code with optimal performance. In this paper, we consider the class of {\em discrete memoryless} source/channel pairs for which a code of finite block length $M$ achieves optimal performance. Somewhat contrary to (initial) intuition, it seems that this class is not larger than ${\mathbb S}$. [ps]
     
     
119. Servetto, Sergio D.; Vetterli, Martin   [ServettoV:00a]   [published]
     Video multicast over fair queueing networks    
     International Conference on Image Processing, vol. 3, p. 540-543
     We consider the problem of video multicast over networks that enforce fair bandwidth allocations in the routers. State-of-the-art layered IP multicast systems perform well for moderately sized sessions, but suffer from three basic problems that prevent their massive deployment: (a) lack of fairness among different multicast sessions, (b) lack of fairness to competing TCP flows, and (c) high complexity requirements to scale up to potentially large numbers of users and sessions. In this work we present an entirely different approach to the design of these systems, in which sources obliviously inject packets into the network (disregarding congestion), whereas routers obliviously drop the amount of bandwidth that exceeds the fair share of a flow (disregarding packet contents). We model our system as a broadcast channel, with receivers connected to the source via erasure channels of different capacities, and we design a video coder to operate in this environment. Our results suggest that a combination of fair queueing routers and appropriate coding is indeed able to overcome certain drawbacks of current IP multicast systems. Furthermore, we also find that such systems would benefit significantly from being able to re-encode the video signal at internal nodes of the multicast tree. [ps]
     
     
120. Gastpar, Michael; Rimoldi, Bixio; Vetterli, Martin   [GastparRV:00a]   [published]
     To code or not to code    
     IEEE International Symposium on Information Theory, p. 236
     The theory and practice of digital communication during the past 50 years has been strongly influenced by Shannon's separation theorem. While it is conceptually and practically appealing to separate source from channel coding, either step requires infinite delay in general for optimal performance. On the other extreme is uncoded transmission, which has no delay but is suboptimal in general. In this paper, necessary and sufficient conditions for the optimality of uncoded transmission are shown. These conditions allow the construction of arbitrary examples of optimal uncoded transmission (beyond the well-known Gaussian example). [ps]
     
     
121. Servetto, Sergio D.; Vetterli, Martin   [ServettoV:00b]   [published]
     High-bandwidth internet video telephony    
     Proc. IEEE Packet Video Workshop
     We consider the problem of full-duplex video transmission over the Internet, under real-time delay constraints. In this work we present the design of a complete communications system, whose salient features are: (a) a soft real-time transport protocol, whose generated traffic characteristics are identical to those of bulk transfers using TCP/IP, thus ensuring complete fairness to other flows in the network; (b) a video coder resilient to moderate amounts of loss of data that are induced by the soft real-time constraint, and also by a continuous probing of the available channel capacity; (c) a unified control module, responsible for both congestion avoidance as well as coder configuration tasks; and (d) very low computational complexity. A key component of our system design is a predictive multiple description video coder working under feedback control. The whole system is implemented on a Linux PC, only in software, without making use of priviliged system calls (e.g., to raise the priority of a process). Using our prototype system, over certain high-speed segments of the public network we were able to deliver YUV signals of size 352x240 pixels, at about 15-25 frames/sec, and at average bit rates in the range of 0.5-1.5 Mbits/sec. [ps]
     
     
122. Dragotti, Pier Luigi; Servetto, Sergio D.; Vetterli, Martin   [DragottiSV:00]   [published]
     Analysis of optimal filter banks for multiple description coding    
     Proc. Data Compression Conference, p. 323-332
     We study the problem of multiple description (MD) coding of stationary Gaussian sources with memory. First, we compute an approximate rate distortion region for these sources, which we prove to be asymptotically tight at high rates: this region generalizes the standard MD rate distortion region for memoryless sources. Then we develop an algorithm for the design of optimal biorthogonal filter banks for MD coding. Finally. We present some experimental results, where we measure the deviation from optimality of our proposed system. For almost uncorrelated sources the gap between the performance of our proposed system and the ideal bounds is quite high, on the other hand for highly correlated sources this gap is reduced, due to the ability of our system to take advantage of the memory in the source. In this case, in realistic scenarios where finite complexity/delay is an issue, the subband coding approach is competitive with other approaches such as the decorrelating transform followed by MD scalar quantizers. [ps]