ALBERT

Description: Manifold learning and dimensionality reduction techniques are ubiquitous in science and engineering, but can be computationally expensive procedures when applied to large datasets or when similarities are expensive to compute. To date, little work has been done to investigate the tradeoff between computational resources and the quality of learned representations. We present both theoretical and experimental explorations of this question. In particular, we consider Laplacian eigenmaps embeddings based on a kernel matrix, and explore how the embeddings behave when this kernel matrix is corrupted by occlusion and noise. Our main theoretical result shows that under modest noise and occlusion assumptions, we can (with high probability) recover a good approximation to the Laplacian eigenmaps embedding based on the uncorrupted kernel matrix. Our results also show how regularization can aid this approximation. Experimentally, we explore the effects of noise and occlusion on Laplacian eigenmaps embeddings of two real-world datasets, one from speech processing and one from neuroscience, as well as a synthetic dataset.

Description: This paper is concerned with the problem of low-rank plus sparse matrix decomposition for big data. Conventional algorithms for matrix decomposition use the entire data to extract the low-rank and sparse components, and are based on optimization problems with complexity that scales with the dimension of the data, which limits their scalability. Furthermore, existing randomized approaches mostly rely on uniform random sampling, which is quite inefficient for many real world data matrices that exhibit additional structures (e.g., clustering). In this paper, a scalable subspace-pursuit approach that transforms the decomposition problem to a subspace learning problem is proposed. The decomposition is carried out by using a small data sketch formed from sampled columns/rows. Even when the data are sampled uniformly at random, it is shown that the sufficient number of sampled columns/rows is roughly $mathcal {O}(r mu)$ , where $mu$ is the coherency parameter and $r$ is the rank of the low-rank component. In addition, adaptive sampling algorithms are proposed to address the problem of columns/rows sampling from structured data. We provide an analysis of the proposed method with adaptive sampling and show that adaptive sampling makes the required number of sampled columns/rows invariant to the distribution of the data. The proposed approach is amenable to online implementation and an online scheme is proposed.

Description: Numerous applied problems of two-dimensional (2-D) and 3-D imaging are formulated in continuous domain. They place great emphasis on obtaining and manipulating the Fourier transform in polar and spherical coordinates. However, the translation of continuum ideas with the discrete sampled data on a Cartesian grid is problematic. There exists no exact and fast solution to the problem of obtaining discrete Fourier transform for polar and spherical grids in the literature. In this paper, we develop exact algorithms to the above problem for 2-D and 3-D, which involve only 1-D equispaced fast Fourier transform with no interpolation or approximation at any stage. The result of the proposed approach leads to a fast solution with very high accuracy. We describe the computational procedure to obtain the solution in both 2-D and 3-D, which includes fast forward and inverse transforms. We find the nested multilevel matrix structure of the inverse process, and we propose a hybrid grid and use a preconditioned conjugate gradient method that exhibits a drastic improvement in the condition number.

Description: Sparse recovery aims to reconstruct sparse signals from compressed linear measurements. In this paper, we propose a sparse recovery algorithm called multiple orthogonal least squares (MOLS), which extends the well-known orthogonal least squares (OLS) algorithm by allowing multiple $L$ indices to be selected per iteration. Owing to its ability to catch multiple support indices in each selection, MOLS often converges in fewer iterations and hence improves the computational efficiency over the conventional OLS algorithm. Theoretical analysis shows that MOLS ( $L > 1$ ) performs exact recovery of $K$ -sparse signals ( $K > 1$ ) in at most $K$ iterations, provided that the sensing matrix obeys the restricted isometry property with isometry constant $delta _{LK} 〈 {sqrt{L}}/({sqrt{K} + 2 sqrt{L}}).$ When $L = 1,$ MOLS reduces to the conventional OLS algorithm and our analysis shows that exact recovery is guaranteed under $delta_{K +1} 〈 1 / (sqrt{K} + 2)$ . This condition is nearly optimal with respect to $delta _{K+1}$ in the sense that, even with a small relaxation (e.g., $delta_{K + 1} = 1 / sqrt{K}$ ), exact recovery with OLS may not be guaranteed. The recovery performance of MOLS in the noisy sce- ario is also studied. It is shown that stable recovery of sparse signals can be achieved with the MOLS algorithm when the signal-to-noise ratio scales linearly with the sparsity level of input signals.

Description: Many applications collect a large number of time series, for example, the financial data of companies quoted in a stock exchange, the health care data of all patients that visit the emergency room of a hospital, or the temperature sequences continuously measured by weather stations across the US. These data are often referred to as un structured. The first task in its analytics is to derive a low dimensional representation, a graph or discrete manifold, that describes well the inter relations among the time series and their intra relations across time. This paper presents a computationally tractable algorithm for estimating this graph that structures the data. The resulting graph is directed and weighted, possibly capturing causal relations, not just reciprocal correlations as in many existing approaches in the literature. A convergence analysis is carried out. The algorithm is demonstrated on random graph datasets and real network time series datasets, and its performance is compared to that of related methods. The adjacency matrices estimated with the new method are close to the true graph in the simulated data and consistent with prior physical knowledge in the real dataset tested.

Description: In this paper, we present a novel technique for the retrieval of the modes of a multicomponent signal using a time-frequency (TF) representation of the signal. Our approach is based on a novel ridge extraction method that takes into account the fact that the TF representation is both discrete in time and frequency, followed by a demodulation procedure. Numerical results show the benefits of the proposed approach for mode reconstruction in comparison to similar techniques that do not make use of demodulation. Furthermore, numerical investigations show that the proposed approach sharpens the TF representation on which it is built.

Description: A novel approach termed stochastic truncated amplitude flow (STAF) is developed to reconstruct an unknown $n$ -dimensional real-/complex-valued signal $boldsymbol {x}$ from $m$ “phaseless” quadratic equations of the form $psi _i=|langle boldsymbol {a}_i,boldsymbol {x}rangle |$ . This problem, also known as phase retrieval from magnitude-only information, is NP-hard in general. Adopting an amplitude-based nonconvex formulation, STAF leads to an iterative solver comprising two stages: s1) Orthogonality-promoting initialization through a stochastic variance reduced gradient algorithm; and, s2) a series of iterative refinements of the initialization using stochastic truncated gradient iterations. Both stages involve a single equation per iteration, thus rendering STAF a simple, scalable, and fast approach amenable to large-scale implementations that are useful when $n$ is large. When $lbrace boldsymbol {a}_irbrace _{i=1}^m$ are independent Gaussian, STAF provably recovers exactly any $boldsymbol {x}in mathbb{R}^n$ exponentially fast based on order of $n$ quadratic equations. STAF is also robust in the presence of additive noise of bounded support. Simulated tests involving real Gaussian $lbrace boldsymbol {a}_irbrace$ vectors demonstrate th- t STAF empirically reconstructs any $boldsymbol {x}in mathbb{R}^n$ exactly from about $2.3n$ magnitude-only measurements, outperforming state-of-the-art approaches and narrowing the gap from the information-theoretic number of equations $m=2n-1$ . Extensive experiments using synthetic data and real images corroborate markedly improved performance of STAF over existing alternatives.

Description: We consider a distributed parameter estimation problem, in which multiple terminals send messages related to their local observations using limited rates to a fusion center which obtains an estimate of a parameter related to the observations of all terminals. It is well known that if the transmission rates are in the Slepian–Wolf region, the fusion center can fully recover all observations and hence can construct an estimator having the same performance as that of the centralized case. One natural question is whether Slepian–Wolf rates are necessary to achieve the same estimation performance as that of the centralized case. In this paper, we show that the answer to this question is negative. We establish our result by explicitly constructing an asymptotically minimum variance unbiased estimator that has the same performance as that of the optimal estimator in the centralized case while using information rates less than the conditions required in the Slepian–Wolf rate region. The key idea is that, instead of aiming to recover the observations at the fusion center, we design universal schemes enabling the fusion center to compute a sufficient statistic using rates outside of the Selpian–Wolf region.

Description: We propose two computationally efficient residual Doppler shift estimation methods for underwater acoustic multicarrier communication. The first method is based on computing the phase of the root of a low order polynomial. The second method is a closed-form least squares estimate given the unwrapped phases of the minimal eigenvector of a small data matrix. The complexities of both estimates are significantly lower compared to the methods commonly used in underwater acoustic multicarrier communication, which result in nonlinear least squares estimators and thus require a fine grid search in the frequency domain. Numerical simulations show that the mean square errors of the proposed methods have similar performance as the common estimation techniques, achieve the Cramer–Rao lower bounds at low noise levels, and agree with their theoretically derived variances. Pool experiments and sea trial results further demonstrate that the suggested estimates yield similar results as the common nonlinear least squares estimates but at a lower complexity.

Description: When the noise affecting time series is colored with unknown statistics, a difficulty for sinusoid detection is to control the true significance level of the test outcome. This paper investigates the possibility of using training datasets of the noise to improve this control. Specifically, we analyze the performances of various detectors applied to periodograms standardized using training datasets. Emphasis is put on sparse detection in the Fourier domain and on the limitation posed by the necessarily finite size of the training sets available in practice. We study the resulting false alarm and detection rates and show that standardization leads, in some cases, to powerful constant false alarm rate tests. The study is both analytical and numerical. Although analytical results are derived in an asymptotic regime, numerical results show that theory accurately describes the tests’ behavior for moderately large sample sizes. Throughout the paper, an application of the considered periodogram standardization is presented for exoplanet detection in radial velocity data.