Pinboard (Vaguery)

[2408.03809] A broken duet: multistable dynamics of dyadic interactions

Vaguery — 2024-12-21T14:56:00+00:00

Misunderstandings in dyadic interactions often persist despite our best efforts, particularly between native and non-native speakers, resembling a broken duet that refuses to harmonise. This paper delves into the computational mechanisms underpinning these misunderstandings through the lens of the broken Lorenz system -- a continuous dynamical model. By manipulating a specific parameter regime, we induce bistability within the Lorenz equations, thereby confining trajectories to distinct attractors based on initial conditions. This mirrors the persistence of divergent interpretations that often result in misunderstandings. Our simulations reveal that differing prior beliefs between interlocutors result in misaligned generative models, leading to stable yet divergent states of understanding when exposed to the same percept. Specifically, native speakers equipped with precise (i.e., overconfident) priors expect inputs to align closely with their internal models, thus struggling with unexpected variations. Conversely, non-native speakers with imprecise (i.e., less confident) priors exhibit a greater capacity to adjust and accommodate unforeseen inputs. Our results underscore the important role of generative models in facilitating mutual understanding (i.e., establishing a shared narrative) and highlight the necessity of accounting for multistable dynamics in dyadic interactions.

[2001.04342] Reservoir computing for sensing: an experimental approach

Vaguery — 2024-10-30T12:59:38+00:00

The increasing popularity of machine learning solutions puts increasing restrictions on this field if it is to penetrate more aspects of life. In particular, energy efficiency and speed of operation is crucial, inter alia in portable medical devices. The Reservoir Computing (RC) paradigm poses as a solution to these issues through foundation of its operation: the reservoir of states. Adequate separation of input information translated into the internal state of the reservoir, whose connections do not need to be trained, allow to simplify the readout layer thus significantly accelerating the operation of the system. In this brief review article, the theoretical basis of RC was first described, followed by a description of its individual variants, their development and state-of-the-art applications in chemical sensing and metrology: detection of impedance changes and ion sensing. Presented results indicate applicability of reservoir computing for sensing and validating the SWEET algorithm experimentally.

[2404.04870] Signal-noise separation using unsupervised reservoir computing

Vaguery — 2024-05-27T12:42:10+00:00

Removing noise from a signal without knowing the characteristics of the noise is a challenging task. This paper introduces a signal-noise separation method based on time series prediction. We use Reservoir Computing (RC) to extract the maximum portion of "predictable information" from a given signal. Reproducing the deterministic component of the signal using RC, we estimate the noise distribution from the difference between the original signal and reconstructed one. The method is based on a machine learning approach and requires no prior knowledge of either the deterministic signal or the noise distribution. It provides a way to identify additivity/multiplicativity of noise and to estimate the signal-to-noise ratio (SNR) indirectly. The method works successfully for combinations of various signal and noise, including chaotic signal and highly oscillating sinusoidal signal which are corrupted by non-Gaussian additive/ multiplicative noise. The separation performances are robust and notably outstanding for signals with strong noise, even for those with negative SNR.

[1808.00572] Jumping champions and prime gaps using information-theoretic tools

Vaguery — 2022-05-19T10:41:29+00:00

We study the spacing of the primes using methods from information theory. In information theory, the equivalence of continuous and discrete representations of information is established by Shannon sampling theory. Here, we use Shannon sampling methods to construct continuous functions whose varying bandwidth follows the distribution of the prime numbers. The Fourier transforms of these signals spike at frequently occurring spacings between the primes. We find prominent spikes, in particular, at the primorials. Previously, the primorials have been conjectured to be the most frequent gaps between subsequent primes, the so-called "jumping champions". Here, we find a foreshadowing of the primorial's role as jumping champions in the sense that Fourier spikes for the primorials arise much earlier on the number axis than where the primorials in question are expected to reign as jumping champions.

[2005.04144] Wonders of chaos for communication

Vaguery — 2022-05-14T11:28:46+00:00

This work shows that chaotic signals with different power spectrum are robust to linear superposition, meaning that the superposition preserves Ergodic quantities (Lyapunov exponents) and the information content of the source signals, even after being transmitted over non-ideal physical medium. This wonderful property that chaotic signals have allows me to propose a novel communication system based on chaos, where information composed from and to multiple users each operating with different base frequencies and that is carried by chaotic wavesignals can be fully preserved after transmission in the open air wireless physical medium, and it can be trivially decoded with low probability of errors. This work tackles with great detail how chaotic signals and their information content are affected when travelling through medium that presents the non-ideal properties of multipath propagation, noise and chaotic interference (linear superposition), and how this impacts on the proposed communication system. Physical media with other non-ideal properties (dispersion and interference with periodic signals) are also discussed.

[2010.12962] Voronoi chains, blocks, and clusters in perturbed square lattices

Vaguery — 2022-05-14T11:17:34+00:00

Perturbed lattices provide simple models for studying many physical systems. In this paper we study the distribution of Voronoi chains, blocks, and clusters with prescribed combinatorial features in the perturbed square lattice, generalizing earlier work. In particular, we obtain analytic results for the presence of hexagonally-ordered regions within a square-ordered phase. Connections to high-temperature crystals and to non-equilibrium phase transitions are considered. In an appendix, we briefly consider the site-percolation threshold for this system.

[2101.11208] Statistical guided-waves-based SHM via stochastic non-parametric time series models

Vaguery — 2022-04-02T13:12:01+00:00

Damage detection in active-sensing, guided-waves-based Structural Health Monitoring (SHM) has evolved through multiple eras of development during the past decades. Nevertheless, there still exists a number of challenges facing the current state-of-the-art approaches, both in the industry as well as in research and development, including low damage sensitivity, lack of robustness to uncertainties, need for user-defined thresholds, and non-uniform response across a sensor network. In this work, a novel statistical framework is proposed for active-sensing SHM based on the use of ultrasonic guided waves. This framework is based on stochastic non-parametric time series models and their corresponding statistical properties in order to readily provide healthy confidence bounds and enable accurate and robust damage detection via the use of appropriate statistical decision making tests. Three such methods and corresponding statistical quantities (test statistics) along with decision making schemes are formulated and experimentally assessed via the use of three coupons with different levels of complexity: an Al plate with a growing notch, a Carbon fiber-reinforced plastic (CFRP) plate with added weights to simulate local damages, and the CFRP panel used in the Open Guided Waves project [1], all fitted with piezoelectric transducers and a pitch-catch configuration. The performance of the proposed methods is compared to that of state-of-the-art time-domain damage indices (DIs). The results demonstrate the increased sensitivity and robustness of the proposed methods, with better tracking capability of damage evolution compared to conventional approaches, even for damage-non-intersecting actuator-sensor paths. Overall, the proposed statistical methods exhibit greater damage sensitivity across different components, with enhanced robustness to uncertainty, as well as user-friendly application.

[1708.05223] The streaming $k$-mismatch problem

Vaguery — 2022-02-28T14:03:37+00:00

We consider the streaming complexity of a fundamental task in approximate pattern matching: the k-mismatch problem. It asks to compute Hamming distances between a pattern of length n and all length-n substrings of a text for which the Hamming distance does not exceed a given threshold k. In our problem formulation, we report not only the Hamming distance but also, on demand, the full \emph{mismatch information}, that is the list of mismatched pairs of symbols and their indices. The twin challenges of streaming pattern matching derive from the need both to achieve small working space and also to guarantee that every arriving input symbol is processed quickly. We present a streaming algorithm for the k-mismatch problem which uses O(klognlognk) bits of space and spends \ourcomplexity time on each symbol of the input stream, which consists of the pattern followed by the text. The running time almost matches the classic offline solution and the space usage is within a logarithmic factor of optimal. Our new algorithm therefore effectively resolves and also extends an open problem first posed in FOCS'09. En route to this solution, we also give a deterministic O(k(lognk+log|Σ|))-bit encoding of all the alignments with Hamming distance at most k of a length-n pattern within a text of length O(n). This secondary result provides an optimal solution to a natural communication complexity problem which may be of independent interest.

[2003.09905] Unsupervised phase discovery with deep anomaly detection

Vaguery — 2022-01-26T13:31:49+00:00

We demonstrate how to explore phase diagrams with automated and unsupervised machine learning to find regions of interest for possible new phases. In contrast to supervised learning, where data is classified using predetermined labels, we here perform anomaly detection, where the task is to differentiate a normal data set, composed of one or several classes, from anomalous data. Asa paradigmatic example, we explore the phase diagram of the extended Bose Hubbard model in one dimension at exact integer filling and employ deep neural networks to determine the entire phase diagram in a completely unsupervised and automated fashion. As input data for learning, we first use the entanglement spectra and central tensors derived from tensor-networks algorithms for ground-state computation and later we extend our method and use experimentally accessible data such as low-order correlation functions as inputs. Our method allows us to reveal a phase-separated region between supersolid and superfluid parts with unexpected properties, which appears in the system in addition to the standard superfluid, Mott insulator, Haldane-insulating, and density wave phases.

[2110.12261] espiownage: Tracking Transients in Steelpan Drum Strikes Using Surveillance Technology

Vaguery — 2022-01-23T12:26:10+00:00

We present an improvement in the ability to meaningfully track features in high speed videos of Caribbean steelpan drums illuminated by Electronic Speckle Pattern Interferometry (ESPI). This is achieved through the use of up-to-date computer vision libraries for object detection and image segmentation as well as a significant effort toward cleaning the dataset previously used to train systems for this application. Besides improvements on previous metric scores by 10% or more, noteworthy in this project are the introduction of a segmentation-regression map for the entire drum surface yielding interference fringe counts comparable to those obtained via object detection, as well as the accelerated workflow for coordinating the data-cleaning-and-model-training feedback loop for rapid iteration allowing this project to be conducted on a timescale of only 18 days.

[1802.06095] Mining Sub-Interval Relationships In Time Series Data

Vaguery — 2021-05-11T19:03:28+00:00

Time-series data is being increasingly collected and stud- ied in several areas such as neuroscience, climate science, transportation, and social media. Discovery of complex patterns of relationships between individual time-series, using data-driven approaches can improve our understanding of real-world systems. While traditional approaches typically study relationships between two entire time series, many interesting relationships in real-world applications exist in small sub-intervals of time while remaining absent or feeble during other sub-intervals. In this paper, we define the notion of a sub-interval relationship (SIR) to capture inter- actions between two time series that are prominent only in certain sub-intervals of time. We propose a novel and efficient approach to find most interesting SIR in a pair of time series. We evaluate our proposed approach on two real-world datasets from climate science and neuroscience domain and demonstrated the scalability and computational efficiency of our proposed approach. We further evaluated our discovered SIRs based on a randomization based procedure. Our results indicated the existence of several such relationships that are statistically significant, some of which were also found to have physical interpretation.

[1905.03330] Universal Sound Separation

Vaguery — 2020-05-21T11:49:53+00:00

Recent deep learning approaches have achieved impressive performance on speech enhancement and separation tasks. However, these approaches have not been investigated for separating mixtures of arbitrary sounds of different types, a task we refer to as universal sound separation, and it is unknown how performance on speech tasks carries over to non-speech tasks. To study this question, we develop a dataset of mixtures containing arbitrary sounds, and use it to investigate the space of mask-based separation architectures, varying both the overall network architecture and the framewise analysis-synthesis basis for signal transformations. These network architectures include convolutional long short-term memory networks and time-dilated convolution stacks inspired by the recent success of time-domain enhancement networks like ConvTasNet. For the latter architecture, we also propose novel modifications that further improve separation performance. In terms of the framewise analysis-synthesis basis, we explore both a short-time Fourier transform (STFT) and a learnable basis, as used in ConvTasNet. For both of these bases, we also examine the effect of window size. In particular, for STFTs, we find that longer windows (25-50 ms) work best for speech/non-speech separation, while shorter windows (2.5 ms) work best for arbitrary sounds. For learnable bases, shorter windows (2.5 ms) work best on all tasks. Surprisingly, for universal sound separation, STFTs outperform learnable bases. Our best methods produce an improvement in scale-invariant signal-to-distortion ratio of over 13 dB for speech/non-speech separation and close to 10 dB for universal sound separation.

[1706.00399] Benchmark problems for phase retrieval

Vaguery — 2020-04-22T23:14:41+00:00

In recent years, the mathematical and algorithmic aspects of the phase retrieval problem have received considerable attention. Many papers in this area mention crystallography as a principal application. In crystallography, the signal to be recovered is periodic and comprised of atomic distributions arranged homogeneously in the unit cell of the crystal. The crystallographic problem is both the leading application and one of the hardest forms of phase retrieval. We have constructed a graded set of benchmark problems for evaluating algorithms that perform this type of phase retrieval. The data, publicly available online, is provided in an easily interpretable format. We also propose a simple and unambiguous success/failure criterion based on the actual needs in crystallography. Baseline runtimes were obtained with an iterative algorithm that is similar but more transparent than those used in crystallography. Empirically, the runtimes grow exponentially with respect to a new hardness parameter: the sparsity of the signal autocorrelation. We also review the algorithms used by the leading software packages. This set of benchmark problems, we hope, will encourage the development of new algorithms for the phase retrieval problem in general, and crystallography in particular.

[1203.3353] Solving Structure with Sparse, Randomly-Oriented X-ray Data

Vaguery — 2020-01-19T15:45:09+00:00

Single-particle imaging experiments of biomolecules at x-ray free-electron lasers (XFELs) require processing of hundreds of thousands (or more) of images that contain very few x-rays. Each low-flux image of the diffraction pattern is produced by a single, randomly oriented particle, such as a protein. We demonstrate the feasibility of collecting data at these extremes, averaging only 2.5 photons per frame, where it seems doubtful there could be information about the state of rotation, let alone the image contrast. This is accomplished with an expectation maximization algorithm that processes the low-flux data in aggregate, and without any prior knowledge of the object or its orientation. The versatility of the method promises, more generally, to redefine what measurement scenarios can provide useful signal in the high-noise regime.

[1107.4030] Three dimensional structure from intensity correlations

Vaguery — 2020-01-19T14:39:02+00:00

We develop the analysis of x-ray intensity correlations from dilute ensembles of identical particles in a number of ways. First, we show that the 3D particle structure can be determined if the particles can be aligned with respect to a single axis having a known angle with respect to the incident beam. Second, we clarify the phase problem in this setting and introduce a data reduction scheme that assesses the integrity of the data even before the particle reconstruction is attempted. Finally, we describe an algorithm that reconstructs intensity and particle density simultaneously, thereby making maximal use of the available constraints.

[math/0111080] Phase retrieval by iterated projections

Vaguery — 2019-09-08T12:44:53+00:00

Several strategies in phase retrieval are unified by an iterative "difference map" constructed from a pair of elementary projections and a single real parameter β. For the standard application in optics, where the two projections implement Fourier modulus and object support constraints respectively, the difference map reproduces the "hybrid" form of Fienup's input-output map for β=1. Other values of β are equally effective in retrieving phases but have no input-output counterparts. The geometric construction of the difference map illuminates the distinction between its fixed points and the recovered object, as well as the mechanism whereby stagnation is avoided. When support constraints are replaced by object histogram or atomicity constraints, the difference map lends itself to crystallographic phase retrieval. Numerical experiments with synthetic data suggest that structures with hundreds of atoms can be solved.

[1711.03247] The nonsmooth landscape of phase retrieval

Vaguery — 2019-07-23T20:30:39+00:00

We consider a popular nonsmooth formulation of the real phase retrieval problem. We show that under standard statistical assumptions, a simple subgradient method converges linearly when initialized within a constant relative distance of an optimal solution. Seeking to understand the distribution of the stationary points of the problem, we complete the paper by proving that as the number of Gaussian measurements increases, the stationary points converge to a codimension two set, at a controlled rate. Experiments on image recovery problems illustrate the developed algorithm and theory.

[1811.09620] TimbreTron: A WaveNet(CycleGAN(CQT(Audio))) Pipeline for Musical Timbre Transfer

Vaguery — 2018-12-10T13:43:35+00:00

In this work, we address the problem of musical timbre transfer, where the goal is to manipulate the timbre of a sound sample from one instrument to match another instrument while preserving other musical content, such as pitch, rhythm, and loudness. In principle, one could apply image-based style transfer techniques to a time-frequency representation of an audio signal, but this depends on having a representation that allows independent manipulation of timbre as well as high-quality waveform generation. We introduce TimbreTron, a method for musical timbre transfer which applies "image" domain style transfer to a time-frequency representation of the audio signal, and then produces a high-quality waveform using a conditional WaveNet synthesizer. We show that the Constant Q Transform (CQT) representation is particularly well-suited to convolutional architectures due to its approximate pitch equivariance. Based on human perceptual evaluations, we confirmed that TimbreTron recognizably transferred the timbre while otherwise preserving the musical content, for both monophonic and polyphonic samples.

[1704.03636] Energy Propagation in Deep Convolutional Neural Networks

Vaguery — 2018-03-10T13:14:23+00:00

Many practical machine learning tasks employ very deep convolutional neural networks. Such large depths pose formidable computational challenges in training and operating the network. It is therefore important to understand how fast the energy contained in the propagated signals (a.k.a. feature maps) decays across layers. In addition, it is desirable that the feature extractor generated by the network be informative in the sense of the only signal mapping to the all-zeros feature vector being the zero input signal. This "trivial null-set" property can be accomplished by asking for "energy conservation" in the sense of the energy in the feature vector being proportional to that of the corresponding input signal. This paper establishes conditions for energy conservation (and thus for a trivial null-set) for a wide class of deep convolutional neural network-based feature extractors and characterizes corresponding feature map energy decay rates. Specifically, we consider general scattering networks employing the modulus non-linearity and we find that under mild analyticity and high-pass conditions on the filters (which encompass, inter alia, various constructions of Weyl-Heisenberg filters, wavelets, ridgelets, (α)-curvelets, and shearlets) the feature map energy decays at least polynomially fast. For broad families of wavelets and Weyl-Heisenberg filters, the guaranteed decay rate is shown to be exponential. Moreover, we provide handy estimates of the number of layers needed to have at least ((1−ε)⋅100)% of the input signal energy be contained in the feature vector.

[1802.08435] Efficient Neural Audio Synthesis

Vaguery — 2018-02-27T11:31:12+00:00

Sequential models achieve state-of-the-art results in audio, visual and textual domains with respect to both estimating the data distribution and generating high-quality samples. Efficient sampling for this class of models has however remained an elusive problem. With a focus on text-to-speech synthesis, we describe a set of general techniques for reducing sampling time while maintaining high output quality. We first describe a single-layer recurrent neural network, the WaveRNN, with a dual softmax layer that matches the quality of the state-of-the-art WaveNet model. The compact form of the network makes it possible to generate 24kHz 16-bit audio 4x faster than real time on a GPU. Second, we apply a weight pruning technique to reduce the number of weights in the WaveRNN. We find that, for a constant number of parameters, large sparse networks perform better than small dense networks and this relationship holds for sparsity levels beyond 96%. The small number of weights in a Sparse WaveRNN makes it possible to sample high-fidelity audio on a mobile CPU in real time. Finally, we propose a new generation scheme based on subscaling that folds a long sequence into a batch of shorter sequences and allows one to generate multiple samples at once. The Subscale WaveRNN produces 16 samples per step without loss of quality and offers an orthogonal method for increasing sampling efficiency.

[1802.08370] Do WaveNets Dream of Acoustic Waves?

Vaguery — 2018-02-27T11:25:59+00:00

Various sources have reported the WaveNet deep learning architecture being able to generate high-quality speech, but to our knowledge there haven't been studies on the interpretation or visualization of trained WaveNets. This study investigates the possibility that WaveNet understands speech by unsupervisedly learning an acoustically meaningful latent representation of the speech signals in its receptive field; we also attempt to interpret the mechanism by which the feature extraction is performed. Suggested by singular value decomposition and linear regression analysis on the activations and known acoustic features (e.g. F0), the key findings are (1) activations in the higher layers are highly correlated with spectral features; (2) WaveNet explicitly performs pitch extraction despite being trained to directly predict the next audio sample and (3) for the said feature analysis to take place, the latent signal representation is converted back and forth between baseband and wideband components.

[1707.06340] On Unlimited Sampling

Vaguery — 2018-02-24T12:04:40+00:00

Shannon's sampling theorem provides a link between the continuous and the discrete realms stating that bandlimited signals are uniquely determined by its values on a discrete set. This theorem is realized in practice using so called analog--to--digital converters (ADCs). Unlike Shannon's sampling theorem, the ADCs are limited in dynamic range. Whenever a signal exceeds some preset threshold, the ADC saturates, resulting in aliasing due to clipping. The goal of this paper is to analyze an alternative approach that does not suffer from these problems. Our work is based on recent developments in ADC design, which allow for ADCs that reset rather than to saturate, thus producing modulo samples. An open problem that remains is: Given such modulo samples of a bandlimited function as well as the dynamic range of the ADC, how can the original signal be recovered and what are the sufficient conditions that guarantee perfect recovery? In this paper, we prove such sufficiency conditions and complement them with a stable recovery algorithm. Our results are not limited to certain amplitude ranges, in fact even the same circuit architecture allows for the recovery of arbitrary large amplitudes as long as some estimate of the signal norm is available when recovering. Numerical experiments that corroborate our theory indeed show that it is possible to perfectly recover function that takes values that are orders of magnitude higher than the ADC's threshold.

[1704.07422] Iterative Methods for Photoacoustic Tomography in Attenuating Acoustic Media

Vaguery — 2017-11-17T13:30:12+00:00

The development of efficient and accurate reconstruction methods is an important aspect of tomographic imaging. In this article, we address this issue for photoacoustic tomography. To this aim, we use models for acoustic wave propagation accounting for frequency dependent attenuation according to a wide class of attenuation laws that may include memory. We formulate the inverse problem of photoacoustic tomography in attenuating medium as an ill-posed operator equation in a Hilbert space framework that is tackled by iterative regularization methods. Our approach comes with a clear convergence analysis. For that purpose we derive explicit expressions for the adjoint problem that can efficiently be implemented. In contrast to time reversal, the employed adjoint wave equation is again damping and, thus has a stable solution. This stability property can be clearly seen in our numerical results. Moreover, the presented numerical results clearly demonstrate the Efficiency and accuracy of the derived iterative reconstruction algorithms in various situations including the limited view case.

[1710.00479] Factor selection by permutation

Vaguery — 2017-10-24T11:10:16+00:00

Researchers often have data measuring features xij of samples, such as test scores of students. In factor analysis and PCA, these features are thought to be influenced by unobserved factors, such as skills. Can we determine how many factors affect the data? Many approaches have been developed for this factor selection problem. The popular Parallel Analysis method randomly permutes each feature of the data. It selects factors if their singular values are larger than those of the permuted data. It is used by leading applied statisticians, including T Hastie, M Stephens, J Storey, R Tibshirani and WH Wong. Despite empirical evidence for its accuracy, there is currently no theoretical justification. This prevents us from knowing when it will work in the future. In this paper, we show that parallel analysis consistently selects the significant factors in certain high-dimensional factor models. The intuition is that permutations keep the noise invariant, while "destroying" the low-rank signal. This provides justification for permutation methods in PCA and factor models under some conditions. A key requirement is that the factors must load on several variables. Our work points to improvements of permutation methods.

[1312.5444] Blind Denoising with Random Greedy Pursuits

Vaguery — 2017-10-20T12:33:36+00:00

Denoising methods require some assumptions about the signal of interest and the noise. While most denoising procedures require some knowledge about the noise level, which may be unknown in practice, here we assume that the signal expansion in a given dictionary has a distribution that is more heavy-tailed than the noise. We show how this hypothesis leads to a stopping criterion for greedy pursuit algorithms which is independent from the noise level. Inspired by the success of ensemble methods in machine learning, we propose a strategy to reduce the variance of greedy estimates by averaging pursuits obtained from randomly subsampled dictionaries. We call this denoising procedure Blind Random Pursuit Denoising (BIRD). We offer a generalization to multidimensional signals, with a structured sparse model (S-BIRD). The relevance of this approach is demonstrated on synthetic and experimental MEG signals where, without any parameter tuning, BIRD outperforms state-of-the-art algorithms even when they are informed by the noise level. Code is available to reproduce all experiments.

[1704.08326] Multidimensional Rational Covariance Extension with Approximate Covariance Matching

Vaguery — 2017-09-26T11:04:31+00:00

In our companion paper "Multidimensional rational covariance extension with applications to spectral estimation and image compression" we discussed the multidimensional rational covariance extension problem (RCEP), which has important applications in image processing, and spectral estimation in radar, sonar, and medical imaging. This is an inverse problem where a power spectrum with a rational absolutely continuous part is reconstructed from a finite set of moments. However, in most applications these moments are determined from observed data and are therefore only approximate, and RCEP may not have a solution. In this paper we extend the results to handle approximate covariance matching. We consider two problems, one with a soft constraint and the other one with a hard constraint, and show that they are connected via a homeomorphism. We also demonstrate that the problems are well-posed and illustrate the theory by examples in spectral estimation and texture generation.

[1703.09452] SEGAN: Speech Enhancement Generative Adversarial Network

Vaguery — 2017-09-09T12:40:30+00:00

Current speech enhancement techniques operate on the spectral domain and/or exploit some higher-level feature. The majority of them tackle a limited number of noise conditions and rely on first-order statistics. To circumvent these issues, deep networks are being increasingly used, thanks to their ability to learn complex functions from large example sets. In this work, we propose the use of generative adversarial networks for speech enhancement. In contrast to current techniques, we operate at the waveform level, training the model end-to-end, and incorporate 28 speakers and 40 different noise conditions into the same model, such that model parameters are shared across them. We evaluate the proposed model using an independent, unseen test set with two speakers and 20 alternative noise conditions. The enhanced samples confirm the viability of the proposed model, and both objective and subjective evaluations confirm the effectiveness of it. With that, we open the exploration of generative architectures for speech enhancement, which may progressively incorporate further speech-centric design choices to improve their performance.

[1706.04671] Feature Enhancement in Visually Impaired Images

Vaguery — 2017-08-07T11:21:36+00:00

One of the major open problems in computer vision is detection of features in visually impaired images. In this paper, we describe a potential solution using Phase Stretch Transform, a new computational approach for image analysis, edge detection and resolution enhancement that is inspired by the physics of the photonic time stretch technique. We mathematically derive the intrinsic nonlinear transfer function and demonstrate how it leads to (1) superior performance at low contrast levels and (2) a reconfigurable operator for hyper-dimensional classification. We prove that the Phase Stretch Transform equalizes the input image brightness across the range of intensities resulting in a high dynamic range in visually impaired images. We also show further improvement in the dynamic range by combining our method with the conventional techniques. Finally, our results show a method for computation of mathematical derivatives via group delay dispersion operations.

[1704.00224] A Time-Frequency Domain Approach of Heart Rate Estimation From Photoplethysmographic (PPG) Signal

Vaguery — 2017-04-10T09:36:44+00:00

Objective- Heart rate monitoring using wrist type Photoplethysmographic (PPG) signals is getting popularity because of construction simplicity and low cost of wearable devices. The task becomes very difficult due to the presence of various motion artifacts. The objective is to develop algorithms to reduce the effect of motion artifacts and thus obtain accurate heart rate estimation. Methods- Proposed heart rate estimation scheme utilizes both time and frequency domain analyses. Unlike conventional single stage adaptive filter, multi-stage cascaded adaptive filtering is introduced by using three channel accelerometer data to reduce the effect of motion artifacts. Both recursive least squares (RLS) and least mean squares (LMS) adaptive filters are tested. Moreover, singular spectrum analysis (SSA) is employed to obtain improved spectral peak tracking. The outputs from the filter block and SSA operation are logically combined and used for spectral domain heart rate estimation. Finally, a tracking algorithm is incorporated considering neighbouring estimates. Results- The proposed method provides an average absolute error of 1.16 beat per minute (BPM) with a standard deviation of 1.74 BPM while tested on publicly available database consisting of recordings from 12 subjects during physical activities. Conclusion- It is found that the proposed method provides consistently better heart rate estimation performance in comparison to that recently reported by TROIKA, JOSS and SPECTRAP methods. Significance- The proposed method offers very low estimation error and a smooth heart rate tracking with simple algorithmic approach and thus feasible for implementing in wearable devices to monitor heart rate for fitness and clinical purpose.

[1701.07540] Sample Complexity of the Boolean Multireference Alignment Problem

Vaguery — 2017-03-11T13:11:40+00:00

The Boolean multireference alignment problem consists in recovering a Boolean signal from multiple shifted and noisy observations. In this paper we obtain an expression for the error exponent of the maximum A posteriori decoder. This expression is used to characterize the number of measurements needed for signal recovery in the low SNR regime, in terms of higher order autocorrelations of the signal. The characterization is explicit for various signal dimensions, such as prime and even dimensions.

[1703.00371] ste-GAN-ography: Generating Steganographic Images via Adversarial Training

Vaguery — 2017-03-08T13:20:25+00:00

Adversarial training was recently shown to be competitive against supervised learning methods on computer vision tasks, however, studies have mainly been confined to generative tasks such as image synthesis. In this paper, we apply adversarial training techniques to the discriminative task of learning a steganographic algorithm. Steganography is a collection of techniques for concealing information by embedding it within a non-secret medium, such as cover texts or images. We show that adversarial training can produce robust steganographic techniques: our unsupervised training scheme produces a steganographic algorithm that competes with state-of-the-art steganographic techniques, and produces a robust steganalyzer, which performs the discriminative task of deciding if an image contains secret information. We define a game between three parties, Alice, Bob and Eve, in order to simultaneously train both a steganographic algorithm and a steganalyzer. Alice and Bob attempt to communicate a secret message contained within an image, while Eve eavesdrops on their conversation and attempts to determine if secret information is embedded within the image. We represent Alice, Bob and Eve by neural networks, and validate our scheme on two independent image datasets, showing our novel method of studying steganographic problems is surprisingly competitive against established steganographic techniques.

[1701.09180] Deep Stochastic Radar Models

Vaguery — 2017-02-28T12:39:14+00:00

Accurate simulation and validation of advanced driver assistance systems requires accurate sensor models. Modeling automotive radar is complicated by effects such as multipath reflections, interference, reflective surfaces, discrete cells, and attenuation. Detailed radar simulations based on physical principles exist but are computationally intractable for realistic automotive scenes. This paper describes a methodology for the construction of stochastic automotive radar models based on deep learning connected to real-world data. The resulting model exhibits fundamental radar effects while remaining real-time capable.

[1605.08150] Cognitive Dynamic Systems: A Technical Review of Cognitive Radar

Vaguery — 2017-02-28T12:31:13+00:00

We start with the history of cognitive radar, where origins of the PAC, Fuster research on cognition and principals of cognition are provided. Fuster describes five cognitive functions: perception, memory, attention, language, and intelligence. We describe the Perception-Action Cyclec as it applies to cognitive radar, and then discuss long-term memory, memory storage, memory retrieval and working memory. A comparison between memory in human cognition and cognitive radar is given as well. Attention is another function described by Fuster, and we have given the comparison of attention in human cognition and cognitive radar. We talk about the four functional blocks from the PAC: Bayesian filter, feedback information, dynamic programming and state-space model for the radar environment. Then, to show that the PAC improves the tracking accuracy of Cognitive Radar over Traditional Active Radar, we have provided simulation results. In the simulation, three nonlinear filters: Cubature Kalman Filter, Unscented Kalman Filter and Extended Kalman Filter are compared. Based on the results, radars implemented with CKF perform better than the radars implemented with UKF or radars implemented with EKF. Further, radar with EKF has the worst accuracy and has the biggest computation load because of derivation and evaluation of Jacobian matrices. We suggest using the concept of risk management to better control parameters and improve performance in cognitive radar. We believe, spectrum sensing can be seen as a potential interest to be used in cognitive radar and we propose a new approach Probabilistic ICA which will presumably reduce noise based on estimation error in cognitive radar. Parallel computing is a concept based on divide and conquers mechanism, and we suggest using the parallel computing approach in cognitive radar by doing complicated calculations or tasks to reduce processing time.

[1605.06644] Deep convolutional networks on the pitch spiral for musical instrument recognition

Vaguery — 2017-02-28T12:05:52+00:00

Musical performance combines a wide range of pitches, nuances, and expressive techniques. Audio-based classification of musical instruments thus requires to build signal representations that are invariant to such transformations. This article investigates the construction of learned convolutional architectures for instrument recognition, given a limited amount of annotated training data. In this context, we benchmark three different weight sharing strategies for deep convolutional networks in the time-frequency domain: temporal kernels; time-frequency kernels; and a linear combination of time-frequency kernels which are one octave apart, akin to a Shepard pitch spiral. We provide an acoustical interpretation of these strategies within the source-filter framework of quasi-harmonic sounds with a fixed spectral envelope, which are archetypal of musical notes. The best classification accuracy is obtained by hybridizing all three convolutional layers into a single deep learning architecture.

When invisible noise obscures the signal: the consequences of nonlinearity in motion detection | bioRxiv

Vaguery — 2017-02-12T15:27:18+00:00

The motion energy model is the standard account of motion detection in animals from beetles to humans. Despite this common basis, we show here that a difference in the early stages of visual processing between mammals and insects leads this model to make radically different behavioural predictions. In insects, early filtering is spatially lowpass, which makes the surprising prediction that motion detection can be impaired by “invisible” noise, i.e. noise at a spatial frequency that elicits no response when presented on its own as a signal. We confirm this prediction using the optomotor response of praying mantis Sphodromantis lineola. This does not occur in mammals, where spatially bandpass early filtering means that linear systems techniques, such as deriving channel sensitivity from masking functions, remain approximately valid. Counter-intuitive effects such as masking by invisible noise may occur in neural circuits wherever a nonlinearity is followed by a difference operation.

[1701.00694] Mixed one-bit compressive sensing with applications to overexposure correction for CT reconstruction

Vaguery — 2017-02-01T11:56:38+00:00

When a measurement falls outside the quantization or measurable range, it becomes saturated and cannot be used in classical reconstruction methods. For example, in C-arm angiography systems, which provide projection radiography, fluoroscopy, digital subtraction angiography, and are widely used for medical diagnoses and interventions, the limited dynamic range of C-arm flat detectors leads to overexposure in some projections during an acquisition, such as imaging relatively thin body parts (e.g., the knee). Aiming at overexposure correction for computed tomography (CT) reconstruction, we in this paper propose a mixed one-bit compressive sensing (M1bit-CS) to acquire information from both regular and saturated measurements. This method is inspired by the recent progress on one-bit compressive sensing, which deals with only sign observations. Its successful applications imply that information carried by saturated measurements is useful to improve recovery quality. For the proposed M1bit-CS model, alternating direction methods of multipliers is developed and an iterative saturation detection scheme is established. Then we evaluate M1bit-CS on one-dimensional signal recovery tasks. In some experiments, the performance of the proposed algorithms on mixed measurements is almost the same as recovery on unsaturated ones with the same amount of measurements. Finally, we apply the proposed method to overexposure correction for CT reconstruction on a phantom and a simulated clinical image. The results are promising, as the typical streaking artifacts and capping artifacts introduced by saturated projection data are effectively reduced, yielding significant error reduction compared with existing algorithms based on extrapolation.

[1612.08278] Photoacoustic imaging beyond the acoustic diffraction-limit with dynamic speckle illumination and sparse joint support recovery

Vaguery — 2017-01-14T12:44:15+00:00

In deep tissue photoacoustic imaging the spatial resolution is inherently limited by the acoustic wavelength. Recently, it was demonstrated that it is possible to surpass the acoustic diffraction limit by analyzing fluctuations in a set of photoacoustic images obtained under unknown speckle illumination patterns. Here, we purpose an approach to boost reconstruction fidelity and resolution, while reducing the number of acquired images by utilizing a compressed sensing computational reconstruction framework. The approach takes into account prior knowledge of the system response and sparsity of the target structure. We provide proof of principle experiments of the approach and demonstrate that improved performance is obtained when both speckle fluctuations and object priors are used. We numerically study the expected performance as a function of the measurements signal to noise ratio and sample spatial-sparsity. The presented reconstruction framework can be applied to analyze existing photoacoustic experimental datasets containing dynamic fluctuations.

[1610.08401] Universal adversarial perturbations

Vaguery — 2016-10-30T12:36:07+00:00

Given a state-of-the-art deep neural network classifier, we show the existence of a universal (image-agnostic) and very small perturbation vector that causes natural images to be misclassified with high probability. We propose a systematic algorithm for computing universal perturbations, and show that state-of-the-art deep neural networks are highly vulnerable to such perturbations, albeit being quasi-imperceptible to the human eye. We further empirically analyze these universal perturbations and show, in particular, that they generalize very well across neural networks. The surprising existence of universal perturbations reveals important geometric correlations among the high-dimensional decision boundary of classifiers. It further outlines potential security breaches with the existence of single directions in the input space that adversaries can possibly exploit to break a classifier on most natural images.

[1605.07008] madmom: a new Python Audio and Music Signal Processing Library

Vaguery — 2016-08-06T13:33:18+00:00

In this paper, we present madmom, an open-source audio processing and music information retrieval (MIR) library written in Python. madmom features a concise, NumPy-compatible, object oriented design with simple calling conventions and sensible default values for all parameters, which facilitates fast prototyping of MIR applications. Prototypes can be seamlessly converted into callable processing pipelines through madmom's concept of Processors, callable objects that run transparently on multiple cores. Processors can also be serialised, saved, and re-run to allow results to be easily reproduced anywhere. Apart from low-level audio processing, madmom puts emphasis on musically meaningful high-level features. Many of these incorporate machine learning techniques and madmom provides a module that implements some in MIR commonly used methods such as hidden Markov models and neural networks. Additionally, madmom comes with several state-of-the-art MIR algorithms for onset detection, beat, downbeat and meter tracking, tempo estimation, and piano transcription. These can easily be incorporated into bigger MIR systems or run as stand-alone programs.

[1607.05712] Structure-Blind Signal Recovery

Vaguery — 2016-07-25T12:33:08+00:00

We consider the problem of recovering a signal observed in Gaussian noise. If the set of signals is convex and compact, and can be specified beforehand, one can use classical linear estimators that achieve a risk within a constant factor of the minimax risk. However, when the set is unspecified, designing an estimator that is blind to the hidden structure of the signal remains a challenging problem. We propose a new family of estimators to recover signals observed in Gaussian noise. Instead of specifying the set where the signal lives, we assume the existence of a well-performing linear estimator. Proposed estimators enjoy exact oracle inequalities and can be efficiently computed through convex optimization. We present several numerical illustrations that show the potential of the approach.

[1606.00901] Approximate Message Passing with Built-in Parameter Estimation for Sparse Signal Recovery

Vaguery — 2016-07-25T10:43:29+00:00

The approximate message passing (AMP) algorithm shows advantage over conventional convex optimization methods in recovering under-sampled sparse signals. AMP is analytically tractable and has a much lower complexity. However, it requires that the true parameters of the input and output channels are known. In this paper, we propose an AMP algorithm with built-in parameter estimation that jointly estimates the sparse signals along with the parameters by treating them as unknown random variables with simple priors. Specifically, the maximum a posterior (MAP) parameter estimation is presented and shown to produce estimations that converge to the true parameter values. Experiments on sparse signal recovery show that the performance of the proposed approach matches that of the oracle AMP algorithm where the true parameter values are known.

[1605.01438] Threshold Selection for Total Variation Denoising

Vaguery — 2016-05-14T13:25:50+00:00

Total variation (TV) denoising is a nonparametric smoothing method that has good properties for preserving sharp edges and contours in objects with spatial structures like natural images. The estimate is sparse in the sense that TV reconstruction leads to a piecewise constant function with a small number of jumps. A threshold parameter controls the number of jumps and the quality of the estimation. In practice, this threshold is often selected by minimizing a goodness-of-fit criterion like cross-validation, which can be costly as it requires solving the high-dimensional and non-differentiable TV optimization problem many times. We propose instead a two step adaptive procedure via a connection to large deviation of stochastic processes. We also give conditions under which TV denoising achieves exact segmentation. We then apply our procedure to denoise a collection of 1D and 2D test signals verifying the effectiveness of our approach in practice.

[1501.01811] Is "Compressed Sensing" compressive? Can it beat the Nyquist Sampling Approach?

Vaguery — 2016-03-26T12:02:58+00:00

Data compression capability of "Compressed sensing (sampling)" in signal discretization is numerically evaluated and found to be far from the theoretical upper bound defined by signal sparsity. It is shown that, for the cases when ordinary sampling with subsequent data compression is prohibitive, there is at least one more efficient, in terms of data compression capability, and more simple and intuitive alternative to Compressed sensing: random sparse sampling and restoration of image band-limited approximations based on energy compaction capability of transforms. It is also shown that assertions that "Compressed sensing" can beat the Nyquist sampling approach are rooted in misinterpretation of the sampling theory.

[1408.0145] A convergence and asymptotic analysis of the generalized symmetric FastICA algorithm

Vaguery — 2016-02-25T12:10:30+00:00

This contribution deals with the generalized symmetric FastICA algorithm in the domain of Independent Component Analysis (ICA). The generalized symmetric version of FastICA has been shown to have the potential to achieve the Cram\'er-Rao Bound (CRB) by allowing the usage of different nonlinearity functions in its parallel implementations of one-unit FastICA. In spite of this appealing property, a rigorous study of the asymptotic error of the generalized symmetric FastICA algorithm is still missing in the community. In fact, all the existing results exhibit certain limitations, such as ignoring the impact of data standardization on the asymptotic statistics or being based on a heuristic approach. In this work, we aim at filling this blank. The first result of this contribution is the characterization of the limits of the generalized symmetric FastICA. It is shown that the algorithm optimizes a function that is a sum of the contrast functions used by traditional one-unit FastICA with a correction of the sign. Based on this characterization, we derive a closed-form analytic expression of the asymptotic covariance matrix of the generalized symmetric FastICA estimator using the method of estimating equation and M-estimator.

[1506.06572] Stochastic evolutionary games in dynamic populations

Vaguery — 2016-02-17T11:19:44+00:00

Frequency dependent selection and demographic fluctuations play important roles in evolutionary and ecological processes. Under frequency dependent selection, the average fitness of the population may increase or decrease based on interactions between individuals within the population. This should be reflected in fluctuations of the population size even in constant environments. Here, we propose a stochastic model, which naturally combines these two evolutionary ingredients by assuming frequency dependent competition between different types in an individual-based model. In contrast to previous game theoretic models, the carrying capacity of the population and thus the population size is determined by pairwise competition of individuals mediated by evolutionary games and demographic stochasticity. In the limit of infinite population size, the averaged stochastic dynamics is captured by the deterministic competitive Lotka-Volterra equations. In small populations, demographic stochasticity may instead lead to the extinction of the entire population. As the population size is driven by the fitness in evolutionary games, a population of cooperators is less prone to go extinct than a population of defectors, whereas in the usual systems of fixed size, the population would thrive regardless of its average payoff.

[1506.06138] The evolution of lossy compression

Vaguery — 2016-02-17T09:53:15+00:00

In complex environments, there are costs to both ignorance and perception. An organism needs to track fitness-relevant information about its world, but the more information it tracks, the more resources it must devote to memory and processing. Rate-distortion theory shows that, when errors are allowed, remarkably efficient internal representations can be found by biologically-plausible hill-climbing mechanisms. We identify two regimes: a high-fidelity regime where perceptual costs scale logarithmically with environmental complexity, and a low-fidelity regime where perceptual costs are, remarkably, independent of the environment. When environmental complexity is rising, Darwinian evolution should drive organisms to the threshold between the high- and low-fidelity regimes. Organisms that code efficiently will find themselves able to make, just barely, the most subtle distinctions in their environment.

[1412.7012] Boltzmann-machine learning of prior distributions of binarized natural images

Vaguery — 2015-12-21T12:06:00+00:00

Prior distributions of binarized natural images are learned by using Boltzmann machine. We find that there emerges a structure with two sublattices in the interactions, and the nearest-neighbor and next-nearest-neighbor interactions correspondingly take two discriminative values, which reflects individual characteristics of three sets of pictures we treat. On the other hand, in a longer spacial scale, a longer-range (though still rapidly-decaying) ferromagnetic interaction commonly appear in all the cases. The characteristic length scale of the interactions is universally about up to four lattice spacing ξ≈4. These results are derived by using the mean-field method which effectively reduces the computational time required in Boltzmann machine. An improved mean-field method called the Bethe approximation also gives the same result, which reinforces the validity of our analysis and findings. Relations to criticality, frustration, and simple-cell receptive fields are also discussed.

[1509.04537] Accelerated filtering on graphs using Lanczos method

Vaguery — 2015-12-14T13:43:58+00:00

Signal-processing on graphs has developed into a very active field of research during the last decade. In particular, the number of applications using frames constructed from graphs, like wavelets on graphs, has substantially increased. To attain scalability for large graphs, fast graph-signal filtering techniques are needed. In this contribution, we propose an accelerated algorithm based on the Lanczos method that adapts to the Laplacian spectrum without explicitly computing it. The result is an accurate, robust, scalable and efficient algorithm. Compared to existing methods based on Chebyshev polynomials, our solution achieves higher accuracy without increasing the overall complexity significantly. Furthermore, it is particularly well suited for graphs with large spectral gaps.

[1310.4945] A novel sparsity and clustering regularization

Vaguery — 2015-12-13T14:44:28+00:00

We propose a novel SPARsity and Clustering (SPARC) regularizer, which is a modified version of the previous octagonal shrinkage and clustering algorithm for regression (OSCAR), where, the proposed regularizer consists of a K-sparse constraint and a pair-wise ℓ∞ norm restricted on the K largest components in magnitude. The proposed regularizer is able to separably enforce K-sparsity and encourage the non-zeros to be equal in magnitude. Moreover, it can accurately group the features without shrinking their magnitude. In fact, SPARC is closely related to OSCAR, so that the proximity operator of the former can be efficiently computed based on that of the latter, allowing using proximal splitting algorithms to solve problems with SPARC regularization. Experiments on synthetic data and with benchmark breast cancer data show that SPARC is a competitive group-sparsity inducing regularizer for regression and classification.

[1507.02075] A Simultaneous Sparse Approximation Method for Multidimensional Harmonic Retrieval

Vaguery — 2015-12-10T12:30:46+00:00

In this paper, a sparse-based method for the estimation of the parameters of multidimensional (R-D) modal (harmonic or damped) complex signals in noise is presented. The problem is formulated as R simultaneous sparse approximations of multiple 1-D signals. To get a method able to handle large size signals while maintaining a sufficient resolution, a multigrid dictionary refinement technique is associated with the simultaneous sparse approximation problem. The refinement procedure is proved to converge in the single R-D mode case. Then, for the general multiple modes R-D case, the signal tensor model is decomposed in order to handle each mode separately in an iterative scheme. The proposed method does not require an association step since the estimated modes are automatically "paired". We also derive the Cram\'er-Rao lower bounds of the parameters of modal R-D signals. The expressions are given in compact form in the single R-D mode case. Finally, numerical simulations are conducted to demonstrate the effectiveness of the proposed method.

[1506.07933] AccFFT: A library for distributed-memory FFT on CPU and GPU architectures

Vaguery — 2015-12-06T11:28:47+00:00

We present a new library for parallel distributed Fast Fourier Transforms (FFT). Despite the large amount of work on FFTs, we show that significant speedups can be achieved for distributed transforms. The importance of FFT in science and engineering and the advances in high performance computing necessitate further improvements. AccFFT extends existing FFT libraries for x86 architectures (CPUs) and CUDA-enabled Graphics Processing Units (GPUs) to distributed memory clusters using the Message Passing Interface (MPI). Our library uses specifically optimized all-to-all communication algorithms, to efficiently perform the communication phase of the distributed FFT algorithm. The GPU based algorithm, effectively hides the overhead of PCIe transfers. We present numerical results on the Maverick and Stampede platforms at the Texas Advanced Computing Center (TACC) and on the Titan system at the Oak Ridge National Laboratory (ORNL). We compare the CPU version of AccFFT with P3DFFT and PFFT libraries and we show a consistent 2−3× speedup across a range of processor counts and problem sizes. The comparison of the GPU code with FFTE library shows a similar trend with a 2× speedup. The library is tested up to 131K cores and 4,096 GPUs of Titan, and up to 16K cores of Stampede.

[1501.03879] A new ADMM algorithm for the Euclidean median and its application to robust patch regression

Vaguery — 2015-12-05T23:30:35+00:00

The Euclidean Median (EM) of a set of points Ω in an Euclidean space is the point x minimizing the (weighted) sum of the Euclidean distances of x to the points in Ω. While there exits no closed-form expression for the EM, it can nevertheless be computed using iterative methods such as the Wieszfeld algorithm. The EM has classically been used as a robust estimator of centrality for multivariate data. It was recently demonstrated that the EM can be used to perform robust patch-based denoising of images by generalizing the popular Non-Local Means algorithm. In this paper, we propose a novel algorithm for computing the EM (and its box-constrained counterpart) using variable splitting and the method of augmented Lagrangian. The attractive feature of this approach is that the subproblems involved in the ADMM-based optimization of the augmented Lagrangian can be resolved using simple closed-form projections. The proposed ADMM solver is used for robust patch-based image denoising and is shown to exhibit faster convergence compared to an existing solver.

[1508.05593] A Power Variance Test for Nonstationarity in Complex-Valued Signals

Vaguery — 2015-12-05T17:53:30+00:00

We propose a novel algorithm for testing the hypothesis of nonstationarity in complex-valued signals. The implementation uses both the bootstrap and the Fast Fourier Transform such that the algorithm can be efficiently implemented in O(NlogN) time, where N is the length of the observed signal. The test procedure examines the second-order structure and contrasts the observed power variance - i.e. the variability of the instantaneous variance over time - with the expected characteristics of stationary signals generated via the bootstrap method. Our algorithmic procedure is capable of learning different types of nonstationarity, such as jumps or strong sinusoidal components. We illustrate the utility of our test and algorithm through application to turbulent flow data from fluid dynamics.

[1410.0311] $ell_1$-K-SVD: A Robust Dictionary Learning Algorithm With Simultaneous Update

Vaguery — 2015-11-20T11:01:38+00:00

We develop a dictionary learning algorithm by minimizing the ℓ1 distortion metric on the data term, which is known to be robust for non-Gaussian noise contamination. The proposed algorithm exploits the idea of iterative minimization of weighted ℓ2 error. We refer to this algorithm as ℓ1-K-SVD, where the dictionary atoms and the corresponding sparse coefficients are simultaneously updated to minimize the ℓ1 objective, resulting in noise-robustness. We demonstrate through experiments that the ℓ1-K-SVD algorithm results in higher atom recovery rate compared with the K-SVD and the robust dictionary learning (RDL) algorithm proposed by Lu et al., both in Gaussian and non-Gaussian noise conditions. We also show that, for fixed values of sparsity, number of dictionary atoms, and data-dimension, the ℓ1-K-SVD algorithm outperforms the K-SVD and RDL algorithms when the training set available is small. We apply the proposed algorithm for denoising natural images corrupted by additive Gaussian and Laplacian noise. The images denoised using ℓ1-K-SVD are observed to have slightly higher peak signal-to-noise ratio (PSNR) over K-SVD for Laplacian noise, but the improvement in structural similarity index (SSIM) is significant (approximately 0.1) for lower values of input PSNR, indicating the efficacy of the ℓ1 metric.

[1412.4365] Fast Decoding of Projective Reed-Muller Codes by Dividing a Projective Space into Affine Spaces

Vaguery — 2015-11-05T12:31:53+00:00

A projective Reed-Muller (PRM) code, obtained by modifying a (classical) Reed-Muller code with respect to a projective space, is a doubly extended Reed-Solomon code when the dimension of the related projective space is equal to 1. The minimum distance and dual code of a PRM code are known, and some decoding examples have been represented for the case of a low-dimensional projective space. In this study, we construct an efficient decoding algorithm for all PRM codes. For this purpose, we divide a projective space into a union of affine spaces. In addition, we evaluate the computational complexity and number of correctable errors of our algorithm. Finally, we compare the codeword error rate of our algorithm with that of minimum distance decoding.

[1505.01740] Fast Spectral Unmixing based on Dykstra's Alternating Projection

Vaguery — 2015-11-05T02:14:04+00:00

This paper presents a fast spectral unmixing algorithm based on Dykstra's alternating projection. The proposed algorithm formulates the fully constrained least squares optimization problem associated with the spectral unmixing task as an unconstrained regression problem followed by a projection onto the intersection of several closed convex sets. This projection is achieved by iteratively projecting onto each of the convex sets individually, following Dyktra's scheme. The sequence thus obtained is guaranteed to converge to the sought projection. Thanks to the preliminary matrix decomposition and variable substitution, the projection is implemented intrinsically in a subspace, whose dimension is very often much lower than the number of bands. A benefit of this strategy is that the order of the computational complexity for each projection is decreased from quadratic to linear time. Numerical experiments considering diverse spectral unmixing scenarios provide evidence that the proposed algorithm competes with the state-of-the-art, namely when the number of endmembers is relatively small, a circumstance often observed in real hyperspectral applications.

[1502.01038] A Factorization Scheme for Some Discrete Hartley Transform Matrices

Vaguery — 2015-11-04T11:37:59+00:00

Discrete transforms such as the discrete Fourier transform (DFT) and the discrete Hartley transform (DHT) are important tools in numerical analysis. The successful application of transform techniques relies on the existence of efficient fast transforms. In this paper some fast algorithms are derived. The theoretical lower bound on the multiplicative complexity for the DFT/DHT are achieved. The approach is based on the factorization of DHT matrices. Algorithms for short blocklengths such as N∈{3,5,6,12,24} are presented.

[1402.1605] Fast Numerical Nonlinear Fourier Transforms

Vaguery — 2015-11-04T11:31:19+00:00

The nonlinear Fourier transform, which is also known as the forward scattering transform, decomposes a periodic signal into nonlinearly interacting waves. In contrast to the common Fourier transform, these waves no longer have to be sinusoidal. Physically relevant waveforms are often available for the analysis instead. The details of the transform depend on the waveforms underlying the analysis, which in turn are specified through the implicit assumption that the signal is governed by a certain evolution equation. For example, water waves generated by the Korteweg-de Vries equation can be expressed in terms of cnoidal waves. Light waves in optical fiber governed by the nonlinear Schr\"odinger equation (NSE) are another example. Nonlinear analogs of classic problems such as spectral analysis and filtering arise in many applications, with information transmission in optical fiber, as proposed by Yousefi and Kschischang, being a very recent one. The nonlinear Fourier transform is eminently suited to address them -- at least from a theoretical point of view. Although numerical algorithms are available for computing the transform, a "fast" nonlinear Fourier transform that is similarly effective as the fast Fourier transform is for computing the common Fourier transform has not been available so far. The goal of this paper is to address this problem. Two fast numerical methods for computing the nonlinear Fourier transform with respect to the NSE are presented. The first method achieves a runtime of O(D2) floating point operations, where D is the number of sample points. The second method applies only to the case where the NSE is defocusing, but it achieves an O(Dlog2D) runtime. Extensions of the results to other evolution equations are discussed as well.

[1507.07146] A Framework of Sparse Online Learning and Its Applications

Vaguery — 2015-11-03T13:04:15+00:00

The amount of data in our society has been exploding in the era of big data today. In this paper, we address several open challenges of big data stream classification, including high volume, high velocity, high dimensionality, high sparsity, and high class-imbalance. Many existing studies in data mining literature solve data stream classification tasks in a batch learning setting, which suffers from poor efficiency and scalability when dealing with big data. To overcome the limitations, this paper investigates an online learning framework for big data stream classification tasks. Unlike some existing online data stream classification techniques that are often based on first-order online learning, we propose a framework of Sparse Online Classification (SOC) for data stream classification, which includes some state-of-the-art first-order sparse online learning algorithms as special cases and allows us to derive a new effective second-order online learning algorithm for data stream classification. In addition, we also propose a new cost-sensitive sparse online learning algorithm by extending the framework with application to tackle online anomaly detection tasks where class distribution of data could be very imbalanced. We also analyze the theoretical bounds of the proposed method, and finally conduct an extensive set of experiments, in which encouraging results validate the efficacy of the proposed algorithms in comparison to a family of state-of-the-art techniques on a variety of data stream classification tasks.

[1405.0226] Wide-field, high-resolution Fourier ptychographic microscopy

Vaguery — 2015-11-01T10:59:40+00:00

In this article, we report an imaging method, termed Fourier ptychographic microscopy (FPM), which iteratively stitches together a number of variably illuminated, low-resolution intensity images in Fourier space to produce a wide-field, high-resolution complex sample image. By adopting a wavefront correction strategy, the FPM method can also correct for aberrations and digitally extend a microscope's depth-of-focus beyond the physical limitations of its optics. As a demonstration, we built a microscope prototype with a resolution of 0.78 um, a field-of-view of ~120 mm2, and a resolution-invariant depth-of-focus of 0.3 mm (characterized at 632 nm). Gigapixel colour images of histology slides verify FPM's successful operation. The reported imaging procedure transforms the general challenge of high-throughput, high-resolution microscopy from one that is coupled to the physical limitations of the system's optics to one that is solvable through computation.

[1407.2812] Rate-Optimal Detection of Very Short Signal Segments

Vaguery — 2015-09-30T11:57:30+00:00

Motivated by a range of applications in engineering and genomics, we consider in this paper detection of very short signal segments in three settings: signals with known shape, arbitrary signals, and smooth signals. Optimal rates of detection are established for the three cases and rate-optimal detectors are constructed. The detectors are easily implementable and are based on scanning with linear and quadratic statistics. Our analysis reveals both similarities and differences in the strategy and fundamental difficulty of detection among these three settings.

[1411.5713] Testing for high-dimensional geometry in random graphs

Vaguery — 2015-08-29T14:49:52+00:00

We study the problem of detecting the presence of an underlying high-dimensional geometric structure in a random graph. Under the null hypothesis, the observed graph is a realization of an Erd{\H{o}}s-R{\'e}nyi random graph G(n,p). Under the alternative, the graph is generated from the G(n,p,d) model, where each vertex corresponds to a latent independent random vector uniformly distributed on the sphere 𝕊d−1, and two vertices are connected if the corresponding latent vectors are close enough. In the dense regime (i.e., p is a constant), we propose a near-optimal and computationally efficient testing procedure based on a new quantity which we call signed triangles. The proof of the detection lower bound is based on a new bound on the total variation distance between a Wishart matrix and an appropriately normalized GOE matrix. In the sparse regime, we make a conjecture for the optimal detection boundary. We conclude the paper with some preliminary steps on the problem of estimating the dimension in G(n,p,d).

[1505.01668] Distributed Multi-Target Tracking in Autonomous Sensor Networks

Vaguery — 2015-06-15T11:15:37+00:00

Multi-target tracking is an important problem in civilian and military applications. This paper investigates distributed multi-target tracking using autonomous sensor networks. Data association, which arises particularly in multi-object scenarios, can be tackled by various solutions. We consider sequential Monte Carlo implementations of the Probability Hypothesis Density (PHD) filter based on random finite sets. This approach circumvents the data association issue by jointly estimating all targets in the region of interest. To this end, we develop the Multi-Sensor Particle PHD Filter (MS-PPHDF) as well as a distributed version, called Diffusion Particle PHD Filter (D-PPHDF). Their performance is evaluated in terms of the Optimal Subpattern Assignment (OSPA) metric, benchmarked against a distributed extension of the Posterior Cram\'er-Rao Lower Bound (PCRLB), and compared to the performance of an existing distributed PHD Particle Filter.

[1404.0957] Noise-Induced Stabilization of Planar Flows I

Vaguery — 2015-04-13T17:10:04+00:00

We show that the complex-valued ODE z˙t=an+1zn+1+anzn+⋯+a0, which necessarily has trajectories along which the dynamics blows up in finite time, can be stabilized by the addition of an arbitrarily small elliptic, additive Brownian stochastic term. We also show that the stochastic perturbation has a unique invariant measure which is heavy-tailed yet is uniformly, exponentially attracting. The methods turn on the construction of Lyapunov functions. The techniques used in the construction are general and can likely be used in other settings where a Lyapunov function is needed. This is a two-part paper. This paper, Part I, focuses on general Lyapunov methods as applied to a special, simplified version of the problem. Part II of this paper extends the main results to the general setting.

[1207.7219] Random linear multihop relaying in a general field of interferers using spatial Aloha

Vaguery — 2015-04-13T11:01:27+00:00

In our basic model, we study a stationary Poisson pattern of nodes on a line embedded in an independent planar Poisson field of interfering nodes. Assuming slotted Aloha and the signal-to-interference-and-noise ratio capture condition, with the usual power-law path loss model and Rayleigh fading, we explicitly evaluate several local and end-to-end performance characteristics related to the nearest-neighbor packet relaying on this line, and study their dependence on the model parameters (the density of relaying and interfering nodes, Aloha tuning and the external noise power). Our model can be applied in two cases: the first use is for vehicular ad-hoc networks, where vehicles are randomly located on a straight road. The second use is to study a typical route traced in a (general) planar ad-hoc network by some routing mechanism. The approach we have chosen allows us to quantify the non-efficiency of long-distance routing in pure ad-hoc networks and evaluate a possible remedy for it in the form of additional fixed relaying nodes, called road-side units in a vehicular network. It also allows us to consider a more general field of interfering nodes and study the impact of the clustering of its nodes the routing performance. As a special case of a field with more clustering than the Poison field, we consider a Poisson-line field of interfering nodes, in which all the nodes are randomly located on random straight lines. The comparison to our basic model reveals a paradox: clustering of interfering nodes decreases the outage probability of a single (typical) transmission on the route, but increases the mean end-to-end delay.

[1401.0201] Sparse Recovery with Very Sparse Compressed Counting

Vaguery — 2015-03-09T10:59:03+00:00

Compressed sensing (sparse signal recovery) often encounters nonnegative data (e.g., images). Recently we developed the methodology of using (dense) Compressed Counting for recovering nonnegative K-sparse signals. In this paper, we adopt very sparse Compressed Counting for nonnegative signal recovery. Our design matrix is sampled from a maximally-skewed p-stable distribution (00, it suffices to use M= K/(1-exp(-gK) log N measurements, so that all coordinates can be recovered in one scan of the coordinates. If g = 1 (i.e., dense design), then M = K log N. If g= 1/K or 2/K (i.e., very sparse design), then M = 1.58K log N or M = 1.16K log N. This means the design matrix can be indeed very sparse at only a minor inflation of the sample complexity. Interestingly, as p->1, the required number of measurements is essentially M = 2.7K log N, provided g= 1/K. It turns out that this result is a general worst-case bound.

[1310.1076] Compressed Counting Meets Compressed Sensing

Vaguery — 2015-03-09T10:58:18+00:00

Compressed sensing (sparse signal recovery) has been a popular and important research topic in recent years. By observing that natural signals are often nonnegative, we propose a new framework for nonnegative signal recovery using Compressed Counting (CC). CC is a technique built on maximally-skewed p-stable random projections originally developed for data stream computations. Our recovery procedure is computationally very efficient in that it requires only one linear scan of the coordinates. Our analysis demonstrates that, when 00 and C=pi/2 when p=0.5. In particular, when p->0 the required number of measurements is essentially M=K\log N, where K is the number of nonzero coordinates of the signal.

[1405.1194] Quantization and Compressive Sensing

Vaguery — 2015-03-08T10:45:30+00:00

Quantization is an essential step in digitizing signals, and, therefore, an indispensable component of any modern acquisition system. This book chapter explores the interaction of quantization and compressive sensing and examines practical quantization strategies for compressive acquisition systems. Specifically, we first provide a brief overview of quantization and examine fundamental performance bounds applicable to any quantization approach. Next, we consider several forms of scalar quantizers, namely uniform, non-uniform, and 1-bit. We provide performance bounds and fundamental analysis, as well as practical quantizer designs and reconstruction algorithms that account for quantization. Furthermore, we provide an overview of Sigma-Delta (ΣΔ) quantization in the compressed sensing context, and also discuss implementation issues, recovery algorithms and performance bounds. As we demonstrate, proper accounting for quantization and careful quantizer design has significant impact in the performance of a compressive acquisition system.

[1407.0803] Acoustic Fingerprinting Revisited: Generate Stable Device ID Stealthy with Inaudible Sound

Vaguery — 2015-03-05T11:03:34+00:00

The popularity of mobile device has made people's lives more convenient, but threatened people's privacy at the same time. As end users are becoming more and more concerned on the protection of their private information, it is even harder to track a specific user using conventional technologies. For example, cookies might be cleared by users regularly. Apple has stopped apps accessing UDIDs, and Android phones use some special permission to protect IMEI code. To address this challenge, some recent studies have worked on tracing smart phones using the hardware features resulted from the imperfect manufacturing process. These works have demonstrated that different devices can be differentiated to each other. However, it still has a long way to go in order to replace cookie and be deployed in real world scenarios, especially in terms of properties like uniqueness, robustness, etc. In this paper, we presented a novel method to generate stable and unique device ID stealthy for smartphones by exploiting the frequency response of the speaker. With carefully selected audio frequencies and special sound wave patterns, we can reduce the impacts of non-linear effects and noises, and keep our feature extraction process un-noticeable to users. The extracted feature is not only very stable for a given smart phone speaker, but also unique to that phone. The feature contains rich information that is equivalent to around 40 bits of entropy, which is enough to identify billions of different smart phones of the same model. We have built a prototype to evaluate our method, and the results show that the generated device ID can be used as a replacement of cookie.

[1302.5729] Sparse Signal Estimation by Maximally Sparse Convex Optimization

Vaguery — 2015-02-14T15:24:31+00:00

This paper addresses the problem of sparsity penalized least squares for applications in sparse signal processing, e.g. sparse deconvolution. This paper aims to induce sparsity more strongly than L1 norm regularization, while avoiding non-convex optimization. For this purpose, this paper describes the design and use of non-convex penalty functions (regularizers) constrained so as to ensure the convexity of the total cost function, F, to be minimized. The method is based on parametric penalty functions, the parameters of which are constrained to ensure convexity of F. It is shown that optimal parameters can be obtained by semidefinite programming (SDP). This maximally sparse convex (MSC) approach yields maximally non-convex sparsity-inducing penalty functions constrained such that the total cost function, F, is convex. It is demonstrated that iterative MSC (IMSC) can yield solutions substantially more sparse than the standard convex sparsity-inducing approach, i.e., L1 norm minimization.