nils-herrmann/clean_scirepeval huggingface dataset:
Euclidean Distance Matrices: Essential theory, algorithms, and applications

Euclidean distance matrices (EDMs) are matrices of the squared distances between points. The definition is deceivingly simple; thanks to their many useful properties, they have found applications in psychometrics, crystallography, machine learning, wireless sensor networks, acoustics, and more. Despite the usefulness of EDMs, they seem to be insufficiently known in the signal processing community. Our goal is to rectify this mishap in a concise tutorial. We review the fundamental properties of EDMs, such as rank or (non)definiteness, and show how the various EDM properties can be used to design algorithms for completing and denoising distance data. Along the way, we demonstrate applications to microphone position calibration, ultrasound tomography, room reconstruction from echoes, and phase retrieval. By spelling out the essential algorithms, we hope to fast-track the readers in applying EDMs to their own problems. The code for all of the described algorithms and to generate the figures in the article is available online at http://lcav.epfl.ch/ivan.dokmanic. Finally, we suggest directions for further research.
Fundamental relations between the LMS algorithm and the DFT

The digital Fourier transform (DFT) and the adaptive least mean square (LMS) algorithm have existed for some time. This paper establishes a connection between them. The result is the "LMS spectrum analyzer," a new means for the calculation of the DFT. The method uses a set of N periodic complex phasors whose frequencies are equally spaced from dc to the sampling frequency. The phasors are weighted and then are summed to generate a reconstructed signal. Weights are adapted to realize a best least squares fit between this reconstructed signal and the input signal whose spectrum is to be estimated. The magnitude squares of the weights correspond to the power spectrum. For a proper choice of adaptation speed, the LMS spectrum analyzer will provide an exact N -sample DFT. New DFT outputs will be available in steady flow after the introduction of each new data sample.
Locating nodes with EASE: last encounter routing in ad hoc networks through mobility diffusion

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 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 node mobility can be exploited to disseminate destination location information 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 N nodes perform independent random walks on a square lattice, the length of the routes computed by EASE are on the same order as the distance between the source and destination even for very large N. Therefore, without exchanging 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.
Wavelets and filter banks: relationships and new results

The discrete version of the wavelet transform, which has recently emerged as a powerful tool for nonstationary signal analysis is closely related to filter banks, which have been studied in digital signal processing. Also, multiresolution signal analysis has been used in image processing. The relationship between these techniques is indicated. It is shown how to construct biorthogonal systems with linear-phase finite impulse response (FIR) filters and with regular analysis and synthesis. Some examples of practical interest are given. The complexity of the discrete wavelet transform is also discussed.<<ETX>>
A study of convex coders with an application to image coding

The concept of convex coding systems is presented together with an application to image coding. A convex coder gives the exact description of a convex set or a group of convex sets in which the input signal is located. The reconstruction is left to the decoder whose role is to pick an estimate in the intersection of these sets. Alternating projections can be used to obtain such estimates which geometrically lie in the intersection of the sets. Convex coding enables us to supplement a criterion of "pleasingness" to the current MSE-oriented criterion. This may be useful for very high compression ratio. An example of convex coding which utilizes the conventional DCT coder as one set is demonstrated and the result shows that the blocking artifacts are efficiently removed.<<ETX>>
Order-Optimal Consensus Through Randomized Path Averaging

Gossip algorithms have recently received significant attention, mainly because they constitute simple and robust message-passing schemes for distributed information processing over networks. However, for many topologies that are realistic for wireless ad-hoc and sensor networks (like grids and random geometric graphs), the standard nearest-neighbor gossip converges as slowly as flooding (O(n2) messages). A recently proposed algorithm called geographic gossip improves gossip efficiency by a √n factor, by exploiting geographic information to enable multihop long-distance communications. This paper proves that a variation of geographic gossip that averages along routed paths, improves efficiency by an additional √n factor, and is order optimal (O(n) messages) for grids and random geometric graphs with high probability. We develop a general technique (travel agency method) based on Markov chain mixing time inequalities which can give bounds on the performance of randomized message-passing algorithms operating over various graph topologies.
Wavelets generated by IIR filter banks

The relation between orthogonal finite impulse response filter banks and orthonormal bases of compactly supported wavelets has been established by Daubechies (1988). Building on this result, the authors use infinite impulse response (IIR) filter banks to construct more general orthonormal wavelet bases, which have infinite support, but rapid decay. They give a complete constructive method which gives all rational orthogonal two-channel filters banks. A family of wavelets is developed which have similar smoothness and moment properties to those of Daubechies. Wavelet bases are derived for the space of piecewise polynomial functions, which are alternatives to the Battle-Lemarie bases (Battle, 1987; Lemarie, 1988) and have the desirable property of being realizable. Relevant design exchanges are presented.<<ETX>>
Distributed Successive Refinement of Multiview Images Using Broadcast Advantage

In environmental monitoring applications, having multiple cameras focus on common scenery increases robustness of the system. To save energy based on user demand, successive refinement image coding is important, as it allows us to progressively request better image quality. By exploiting the broadcast nature and correlation between multiview images, we investigate a two-camera setup and propose a novel two-encoder successive refinement scheme which imitates a ping-pong game. For the bivariate Gaussian case, we prove that this scheme is successively refinable on the theoretical rate-distortion limit of distributed coding (Wagner surface) under arbitrary settings. For stereo-view images, we develop a practical successive refinement coding algorithm using the same idea. The simulation results show that this scheme operates close to the distributed coding bound.
Handheld Reflectance Acquisition of Paintings

Relightable photographs are alternatives to traditional photographs as they provide a richer viewing experience. However, the complex acquisition systems of existing techniques have restricted its usage to specialized setups. We introduce an easy-to-use and affordable solution for using smartphones to acquire the reflectance of paintings and similar almost-planar objects like tablets, engravings and textile. Our goal is to enable interactive relighting of such artifacts by everyone. In our approach, we nonuniformly sample the reflectance functions by moving the LED light of a smartphone, and simultaneously, tracking the position of the smartphone by using its camera. We then propose a compressive-sensing-based approach for reconstructing the light transport matrix from the nonuniformly sampled data. As shown with experiments, we accurately reconstruct the light transport matrix that can then be used to create relightable photographs.
Digital DS-CDMA receivers working below the chip rate

We consider the problem of designing low-complexity digital receivers for CDMA 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 channel estimation and signal detection from a low-dimensional subspace of a received signal, that is, by sampling below the traditional Nyquist rate. By lowering the sampling rate we can reduce computational requirements compared to existing solutions, allow for slower A/D converters and significantly reduce the power consumption of digital receivers. In effect, we use an algorithmic solution to improve hardware specifications in terms of complexity and power.
Adaptive quantization without side information

We propose to extend some of the ideas of adaptive lossless compression to design an adaptive quantization algorithm. Noting that the performance of an arithmetic coder is as good as its estimation of the statistics of the input, we split our quantizer into two building blocks: model estimation and quantizer design. The main idea is that, as long as the model estimation manages to track down the changes in source statistics, a standard quantizer design technique which assumes that the source follows the estimated model can be used. As an example of this type of design we study an adaptive scalar quantization scheme where we impose the restriction that no side information can be sent, i.e. encoder and decoder must perform their adaptation based on the quantized information.<<ETX>>
Tomographic Approach for Parametric Estimation of Local Diffusive Sources and Application to Heat Diffusion

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.
An FIR cascade structure for adaptive linear prediction

An alternative structure for adaptive linear prediction is proposed in which the adaptive filter is replaced by a cascade of independently adapting, low-order stages, and the prediction is generated by means of successive refinements. When the adaptation algorithm for the stages is LMS, the associated short filters are less affected by eigenvalue spread and mode coupling problems and display a faster convergence to their steady-state value. Experimental results show that a cascade of second-order LMS filters is capable of successfully modeling most input signals, with a much smaller MSE than LMS or lattice LMS predictors in the early phase of the adaptation. Other adaptation algorithms can be used for the single stages, whereas the overall computational cost remains linear in the number of stages, and very fast tracking is achieved.
Interval consensus: From quantized gossip to voting

We design distributed and quantized average consensus algorithms on arbitrary connected networks. By construction, quantized algorithms cannot produce a real, analog average. Instead, our algorithm reaches consensus on the quantized interval that contains the average. We prove that this consensus in reached in finite time almost surely. As a byproduct of this convergence result, we show that the majority voting problem is solvable with only 2 bits of memory per agent.
Three dimensional sub-band coding of video

A novel coding scheme has been developed which is based on multidimensional subband coding. The digital video signal is filtered and sub-sampled in all three dimensions (temporally, horizontally and vertically) to yield the subbands, from which the input signal can be losslessly reconstructed in the absence of coding loss. The subbands can be more efficiently coded than the input signal in terms of compression and quality, because the restricted information in each band allows well-tailored encoding. The computational complexity of this coding scheme compares favorably to DCT with interframe prediction and inter/intra frame DPCM. The scheme has an architectural structure suitable for parallel implementation, and it yields high compression with sustained good quality.<<ETX>>
Population size estimation using a few individuals as agents

We conduct an experiment where ten attendees of an open-air music festival are acting as Bluetooth probes. We then construct a parametric statistical model to estimate the total number of visible Bluetooth devices in the festival area. By comparing our estimate with ground truth information provided by probes at the entrances of the festival, we show that the total population can be estimated with a surprisingly low error (1.26% in our experiment), given the small number of agents compared to the area of the festival and the fact that they are regular attendees who move randomly. Also, our statistical model can easily be adapted to obtain more detailed estimates, such as the evolution of the population size over time.
Multichannel sampling of low light level scenes with unknown shifts

Images captured under low-light conditions are noisy as a result of photon statistics and quantization error, among other reasons. Such statistical limitations can be reduced by using pixels with larger areas, but this approach leads to aliasing artifacts. We propose a maximum-likelihood version of super-resolution for low-light conditions in which Fourier image coefficients and unknown spatial shifts between captured frames are estimated iteratively, all in order to produce the single image with high expected fidelity. We illustrate the power of our method on both one-dimensional synthetic data and on two-dimensional medical images.
Calibration Using Matrix Completion With Application to Ultrasound Tomography

We study the application of matrix completion in the process of calibrating physical devices. In particular we propose an algorithm together with reconstruction bounds for calibrating circular ultrasound tomography devices. We use the time-of-flight (ToF) measurements between sensor pairs in a homogeneous medium to calibrate the system. The calibration process consists of a low-rank matrix completion algorithm to de-noise and estimate random and structured missing ToFs, and the classic multi-dimensional scaling method to estimate the sensor positions from the ToF measurements. We provide theoretical bounds on the calibration error. Several simulations are conducted to evaluate the theoretical results presented in this paper.
Estimating Sparse MIMO channels having Common Support

We propose an algorithm (SCS-FRI) to estimate multipath channels with Sparse Common Support (SCS) based on Finite Rate of Innovation (FRI) sampling. In this setup, theoretical lower-bounds are derived, and simulation in a Rayleigh fading environment shows that SCS-FRI gets very close to these bounds. We show how to apply SCS-FRI to OFDM and CDMA downlinks. Recovery of a sparse common support is, among other, especially relevant for channel estimation in a multiple output system or beam-forming from multiple input. The present algorithm is based on a multi-output extension of the Cadzow denoising/annihilating filter method [1, 2].
Time-varying orthonormal tilings of the time-frequency plane

Expansions that give arbitrary orthonormal tilings of the time-frequency plane are considered. These differ from the short-time Fourier transform, wavelet transform, and wavelet packet tilings in that they change over time. It is shown how this can be achieved using time-varying orthogonal tree structures, which preserve orthogonality, even across transitions. One method is based on lapped orthogonal transforms, which makes it possible to change the number of channels in the transform. A second method is based on the construction of orthogonal boundary filters to construct essentially arbitrary tilings. A double-tree algorithm is presented that, for a given signal, decides on the best binary segmentation and on which tree split to use for each segment. That is, it is a joint optimization of time and frequency splitting. The algorithm is optimal for additive cost functions (e.g., rate distortion), which gives the best time-varying bases. Results of experiments on test signals are shown.<<ETX>>
Television by the bit

The various types of advanced television (ATV) are defined, and the most advanced type, high-definition TV (HDTV), is discussed. The present status of HDTV development in the US, Japan, and Europe is examined. Signal processing requirements for HDTV are briefly considered, and the benefits of and prospects for all-digital HDTV are explored. Video compression techniques, implementation issues, and the future of HDTV are also discussed.<<ETX>>
Dimensionality Reduction for Distributed Estimation in the Infinite Dimensional Regime

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 fusion center 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 fusion center 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 us to provide a reverse ldquowater-fillingrdquo perspective to the problem of optimal dimensionality reduction. We illustrate, with a first-order Gauss-Markov model, how our findings allow for the computation of analytical closed-form distortion formulas that provide an accurate estimation of the reconstruction error obtained in the finite-dimensional regime.
Lower bound on the mean-squared error in oversampled quantization of periodic signals using vector quantization analysis

Oversampled analog-to-digital conversion is a technique which permits high conversion resolution using coarse quantization. Classically, by lowpass filtering the quantized oversampled signal, it is possible to reduce the quantization error power in proportion to the oversampling ratio R. In other words, the reconstruction mean-squared error (MSE) is in /spl Oscr/(R/sup -1/). It was recently found that this error reduction is not optimal. Under certain conditions, it was shown on periodic bandlimited signals that an upper bound on the MSE of optimal reconstruction is in /spl Oscr/(R/sup -2/) instead of /spl Oscr/(R/sup -1/). In the present paper, we prove on the same type of signals that the order /spl Oscr/(R/sup -2/) is the theoretical limit of reconstruction as an MSE lower bound. The proof is based on a vector-quantization approach with an analysis of partition cell density.
Adaptive scalar quantization without side information

In this paper, we introduce a novel technique for adaptive scalar quantization. Adaptivity is useful in applications, including image compression, where the statistics of the source are either not known a priori or will change over time. Our algorithm uses previously quantized samples to estimate the distribution of the source, and does not require that side information be sent in order to adapt to changing source statistics. Our quantization scheme is thus backward adaptive. We propose that an adaptive quantizer can be separated into two building blocks, namely, model estimation and quantizer design. The model estimation produces an estimate of the changing source probability density function, which is then used to redesign the quantizer using standard techniques. We introduce nonparametric estimation techniques that only assume smoothness of the input distribution. We discuss the various sources of error in our estimation and argue that, for a wide class of sources with a smooth probability density function (pdf), we provide a good approximation to a "universal" quantizer, with the approximation becoming better as the rate increases. We study the performance of our scheme and show how the loss due to adaptivity is minimal in typical scenarios. In particular, we provide examples and show how our technique can achieve signal-to-noise ratios within 0.05 dB of the optimal Lloyd-Max quantizer for a memoryless source, while achieving over 1.5 dB gain over a fixed quantizer for a bimodal source.
Multiple copy image denoising via wavelet thresholding

This work addresses the recovery of an image from noisy observations when multiple noisy copies of the image are available. The standard method is to compute the average of these copies. Since the wavelet thresholding technique has been shown to effectively denoise a single noisy copy, it is natural to consider combining these two operations of averaging and thresholding. The first important task is to find the optimal ordering. The second issue is the threshold selection for each method. By modeling the signal wavelet coefficients as Laplacian distributed and the noise as Gaussian, our investigation finds the optimal ordering to depend on the number of available copies and on the signal-to-noise ratio. We propose thresholds that are nearly optimal under the assumed model for each ordering. With the optimal and near-optimal thresholds, the two methods yield very similar performance, and both show considerable improvement over merely averaging.