Search

It is known that there exist mathematical problems of practical relevance which cannot be computed on a Turing machine. An important example is the calculation of the first derivative of continuously differentiable functions. This paper precisely classifies the non-computability of the first derivative, and of the maximum-norm of the first derivative in the Zheng-Weihrauch hierarchy. Based on this classification, the paper investigates whether it is possible that a Turing machine detects this non-computability of the first derivative by observing the data of the problem, and whether it is possible to detect upper bounds for the peak value of the first derivative of continuously differentiable functions. So from a practical point of view, the question is whether it is possible to implement an exit-flag functionality for observing non-computability of the first derivative. This paper even studies two different types of exit-flag functionality. A strong one, where the Turing machine always has to stop, and a weak one, where the Turing machine stops if and only if the input lies within the corresponding set of interest. It will be shown that non-computability of the first derivative is not detectable by a Turing machine for two concrete examples, namely for the problem of computing the input–output behavior of simple analog circuits and for solutions of the three-dimensional wave equation. In addition, it is shown that it is even impossible to detect an upper bound for the maximum norm of the first derivative. In particular, it is shown that all three problems are not even semidecidable. Finally, we briefly discuss implications of these results for analog and quantum computing. [ABSTRACT FROM AUTHOR]

As an algorithmic framework, message passing is extremely powerful and has wide applications in the context of different disciplines including communications, coding theory, statistics, signal processing, artificial intelligence and combinatorial optimization. In this paper, we investigate the performance of a message-passing algorithm called min-sum belief propagation (BP) for the vertex-disjoint shortest $k$ -path problem ($k$ -VDSP) on weighted directed graphs, and derive the iterative message-passing update rules. As the main result of this paper, we prove that for a weighted directed graph $G$ of order $n$ , BP algorithm converges to the unique optimal solution of $k$ -VDSP on $G$ within $O(n^{2}w_{max})$ iterations, provided that the weight $w_{e}$ is nonnegative integral for each arc $e\in E(G)$ , where $w_{max}=\max \{w_{e}: e\in E(G)\}$. To the best of our knowledge, this is the first instance where BP algorithm is proved correct for NP-hard problems. Additionally, we establish the extensions of $k$ -VDSP to the case of multiple sources or sinks. [ABSTRACT FROM AUTHOR]

This paper considers structure learning from data with $n$ samples of $p$ variables, assuming that the structure is a forest, using the Chow–Liu algorithm. Specifically, for incomplete data, we construct two model selection algorithms that complete in $O(p^{2})$ steps: one obtains a forest with the maximum posterior probability given the data and the other obtains a forest that converges to the true one as $n$ increases. We show that the two forests are generally different when some values are missing. In addition, we present estimations for benchmark data sets to demonstrate that both algorithms work in realistic situations. Moreover, we derive the conditional entropy provided that no value is missing, and we evaluate the per-sample expected redundancy for the universal coding of incomplete data in terms of the number of non-missing samples. [ABSTRACT FROM AUTHOR]

Approximate message passing (AMP) refers to a class of efficient algorithms for statistical estimation in high-dimensional problems such as compressed sensing and low-rank matrix estimation. This paper analyzes the performance of AMP in the regime where the problem dimension is large but finite. For concreteness, we consider the setting of high-dimensional regression, where the goal is to estimate a high-dimensional vector $\beta _{0}$ from a noisy measurement $y=A \beta _{0} + w$. AMP is a low-complexity, scalable algorithm for this problem. Under suitable assumptions on the measurement matrix $A$ , AMP has the attractive feature that its performance can be accurately characterized in the large system limit by a simple scalar iteration called state evolution. Previous proofs of the validity of state evolution have all been asymptotic convergence results. In this paper, we derive a concentration inequality for AMP with Gaussian matrices with independent and identically distributed (i.i.d.) entries and finite dimension $n \times N$. The result shows that the probability of deviation from the state evolution prediction falls exponentially in $n$. This provides theoretical support for empirical findings that have demonstrated excellent agreement of AMP performance with state evolution predictions for moderately large dimensions. The concentration inequality also indicates that the number of AMP iterations $t$ can grow no faster than order $({\log n}/{\log \log n})$ for the performance to be close to the state evolution predictions with high probability. The analysis can be extended to obtain similar non-asymptotic results for AMP in other settings such as low-rank matrix estimation. [ABSTRACT FROM AUTHOR]

Spectral factorization is an operation which appears in many different engineering applications. This paper studies whether spectral factorization can be algorithmically computed on an abstract machine (a Turing machine). It is shown that there exist computable spectral densities with very good analytic properties (i.e. smooth with finite energy) such that the corresponding spectral factor cannot be determined on a Turing machine. Further, it will be proved that it is impossible to decide algorithmically whether or not a given computable density possesses a computable spectral factor. This negative result has consequences for applications of spectral factorization in computer-aided design, because there it is necessary that this problem be decidable. Conversely, this paper will show that if the logarithm of a computable spectral density belongs to certain Sobolev space of sufficiently smooth functions, then the spectral factor is always computable. As an application, the paper discusses the possibility of calculating the optimal causal Wiener filter on an abstract machine. [ABSTRACT FROM AUTHOR]

This paper analyzes the asymptotic performances of fully distributed sequential hypothesis testing procedures as the type-I and type-II error rates approach zero, in the context of a sensor network without a fusion center. In particular, the sensor network is defined by an undirected graph, where each sensor can observe samples over time, access the information from the adjacent sensors, and perform the sequential test based on its own decision statistic. Different from most literature, the sampling process and the information exchange process in our framework take place simultaneously (or, at least in comparable time-scales), thus cannot be decoupled from one another. Our goal is to achieve second-order asymptotically optimal performance at every sensor, i.e., the average detection delay is within a constant gap from the centralized optimal sequential test as the error rates approach zero for the fixed number of sensors. To that end, a type of test procedure that resembles the well-known sequential probability ratio test (SPRT), termed as distributed SPRT (DSPRT) in this paper, is studied based on two message-passing schemes, respectively. The first scheme features the dissemination of the raw samples. In specific, every sample propagates over the network by being relayed from one sensor to another until it reaches all the sensors in the network. Although the sample propagation-based DSPRT is shown to yield the asymptotically optimal performance at each sensor, it incurs excessive inter-sensor communication overhead due to the exchange of raw samples with index information. The second scheme adopts the consensus algorithm, where the local decision statistic is exchanged between sensors instead of the raw samples, thus significantly lowering the communication requirement compared with the first scheme. In particular, the decision statistic for DSPRT at each sensor is updated by the weighted average of the decision statistics in the neighborhood at every message-passing step. We show that, under certain regularity conditions, the consensus algorithm-based DSPRT also yields the second-order asymptotically optimal performance at all sensors given a fixed number of sensors. Our asymptotic analyses of the two message-passing-based DSPRTs are then corroborated by simulations using the Gaussian and Laplacian samples. [ABSTRACT FROM AUTHOR]

It is a well-known fact that the Discrete Fourier Transform (DFT) \vec X of an arbitrary n -length input signal \vec {x} , can be computed from all the n time-domain samples in O( n\log n) operations via a Fast Fourier Transform (FFT) algorithm. If the spectrum k -sparse (where k\ll n ), can we do better? We show that asymptotically in k and n , when k ), where 0 \leq \delta <1 ), and the support of the non-zero DFT coefficients is uniformly random, the fast fourier aliasing-based sparse transform (FFAST) algorithm, proposed in this paper, computes, with asymptotically high probability, the k non-zero DFT coefficients of from O( k) samples of \vec x in O( k\log k) arithmetic operations. Further, the constants in the big Oh notation for both sample and computational cost are small, e.g., when \delta < 0.99 , which essentially covers a wide range of sub-linear sparsity cases, the sample cost is less than 4 k . Although, in this paper we assume that the samples of the signal \vec x observed by the FFAST are noise-free, a noise-robust extension of the FFAST is provided in a companion (Part II) paper [1]. Our approach is based on filter-less sub-sampling of the input signal using a set of carefully chosen uniform sub-sampling patterns guided by the Chinese Remainder Theorem (CRT). The idea is to cleverly exploit, rather than avoid, the resulting aliasing artifacts induced by sub-sampling. Specifically, the sub-sampling operation on the time-domain signal \vec x is designed to create aliasing patterns of the non-zero coefficients of the spectrum \vec X to “look like” parity-check constraints of a good erasure-correcting sparse-graph code. Next, we show that computing the sparse DFT \vec X is equivalent to decoding of an appropriate sparse-graph code. The sparse-graph codes further permit a fast peeling-style decoding. Consequently, the resulting DFT computation is low in both the sample and the decoding complexity. We analytically connect our proposed CRT-based aliasing framework to random sparse-graph codes, and analyze the performance of our algorithm using density evolution techniques from coding theory. We provide extensive simulation results, that are in tight agreement with our theoretical findings. [ABSTRACT FROM PUBLISHER]

Any sequence of uniformly bounded N\times N Hermitian Toeplitz matrices \{H_{N}\} is asymptotically equivalent to a certain sequence of N\times N circulant matrices \CN\ derived from the Toeplitz matrices in the sense that \left \|{HN- CN }\right \|F = o(\sqrt {N}) as $N\rightarrow \infty $ . This implies that certain collective behaviors of the eigenvalues of each Toeplitz matrix are reflected in those of the corresponding circulant matrix and supports the utilization of the computationally efficient fast Fourier transform (instead of the Karhunen-Loève transform) in applications like coding and filtering. In this paper, we study the asymptotic performance of the individual eigenvalue estimates. We show that the asymptotic equivalence of the circulant and Toeplitz matrices implies the individual asymptotic convergence of the eigenvalues for certain types of Toeplitz matrices. We also show that these estimates asymptotically approximate the largest and smallest eigenvalues for more general classes of Toeplitz matrices. [ABSTRACT FROM AUTHOR]

In this paper, we consider the mixture of sparse linear regressions model. Let $\boldsymbol {\beta }^{(1)},\ldots, \boldsymbol {\beta }^{(L)}\in \mathbb {C} ^{n}$ be $L $ unknown sparse parameter vectors with a total of $K $ non-zero elements. Noisy linear measurements are obtained in the form $y_{i} = \boldsymbol {x}_{i} ^{\mathrm{ H}} \boldsymbol {\beta }^{(\ell _{i})} + w_{i}$ , each of which is generated randomly from one of the sparse vectors with the label $\ell _{i} $ unknown. The goal is to estimate the parameter vectors efficiently with low sample and computational costs. This problem presents significant challenges as one needs to simultaneously solve the demixing problem of recovering the labels $\ell _{i} $ as well as the estimation problem of recovering the sparse vectors $\boldsymbol {\beta }^{(\ell)} $. Our solution to the problem leverages the connection between modern coding theory and statistical inference. We introduce a new algorithm, Mixed-Coloring, which samples the mixture strategically using query vectors $\boldsymbol {x}_{i} $ constructed based on ideas from sparse graph codes. Our novel code design allows for both efficient demixing and parameter estimation. To find $K$ non-zero elements, it is clear that we need at least $\Theta (K)$ measurements, and thus the time complexity is at least $\Theta (K)$. In the noiseless setting, for a constant number of sparse parameter vectors, our algorithm achieves the order-optimal sample and time complexities of $\Theta (K)$. In the presence of Gaussian noise, for the problem with two parameter vectors (i.e., $L = 2$), we show that the Robust Mixed-Coloring algorithm achieves near-optimal $\Theta (K \mathop {\mathrm {polylog}}\nolimits (n))$ sample and time complexities. When $K = \mathcal {O}(n^{\alpha })$ for some constant $\alpha \in (0,1)$ (i.e., $K$ is sublinear in $n$), we can achieve sample and time complexities both sublinear in the ambient dimension. In one of our experiments, to recover a mixture of two regressions with dimension $n = 500$ and sparsity $K = 50$ , our algorithm is more than 300 times faster than EM algorithm, with about one third of its sample cost. 1 The proposed algorithm works even when the noise is non-Gaussian in nature, but the guarantees on sample and time complexities are difficult to obtain. [ABSTRACT FROM AUTHOR]

Phase retrieval refers to the problem of recovering a signal $ {x}_{\star }\in \mathbb {C}^{n}$ from its phaseless measurements $\text {y}_{\text {i}}=| {a}_{i}^{ \mathsf {H}} {x}_{\star }|$ , where $\{ {a}_{\text {i}}\}_{\text {i}=1}^{ {m}}$ are the measurement vectors. Spectral method is widely used for initialization in many phase retrieval algorithms. The quality of spectral initialization can have a major impact on the overall algorithm. In this paper, we focus on the model where $ {A}=[ {a}_{1},\ldots, {a}_{ {m}}]^{ \mathsf {H}}$ has orthonormal columns, and study the spectral initialization under the asymptotic setting $ {m}, {n}\to \infty $ with $ {m}/ {n}\to \delta \in (1,\infty)$. We use the expectation propagation framework to characterize the performance of spectral initialization for Haar distributed matrices. Our numerical results confirm that the predictions of the EP method are accurate for not-only Haar distributed matrices, but also for realistic Fourier based models (e.g. the coded diffraction model). The main findings of this paper are the following: 1) There exists a threshold on $\delta $ (denoted as $\delta _{ \mathrm {weak}}$) below which the spectral method cannot produce a meaningful estimate. We show that $\delta _{ \mathrm {weak}}=2$ for the column-orthonormal model. In contrast, previous results by Mondelli and Montanari show that $\delta _{ \mathrm {weak}}=1$ for the i.i.d. Gaussian model. 2) The optimal design for the spectral method coincides with that for the i.i.d. Gaussian model, where the latter was recently introduced by Luo, Alghamdi and Lu. [ABSTRACT FROM AUTHOR]

Finding the sparse representation of a signal in an overcomplete dictionary has attracted a lot of attention over the past years. This paper studies ProSparse, a new polynomial complexity algorithm that solves the sparse representation problem when the underlying dictionary is the union of a Vandermonde matrix and a banded matrix. Unlike our previous work, which establishes deterministic (worst-case) sparsity bounds for ProSparse to succeed, this paper presents a probabilistic average-case analysis of the algorithm. Based on a generating-function approach, closed-form expressions for the exact success probabilities of ProSparse are given. The success probabilities are also analyzed in the high-dimensional regime. This asymptotic analysis characterizes a sharp phase transition phenomenon regarding the performance of the algorithm. [ABSTRACT FROM AUTHOR]

The fast Fourier transform is the most efficiently known way to compute the discrete Fourier transform (DFT) of an arbitrary n -length signal, and has a computational complexity of O( n\log n) . If the DFT \vec X of the signal \vec x has only $k$ non-zero coefficients (where k< n$ ), can we do better? We addressed this question and presented a novel fast Fourier aliasing-based sparse transform (FFAST) algorithm that cleverly induces sparse-graph alias codes in the DFT domain, via a Chinese-remainder-theorem-guided sub-sampling operation in the time-domain. The induced sparse-graph alias codes are then exploited to devise a fast and iterative onion-peeling style decoder that computes k$ -sparse DFT of an n$ -length signal using only O( k)$ time-domain samples and O( k\log k)$ computations. In this paper, we generalize the FFAST framework by Pawar and Ramchandran to the noisy setting where the time-domain samples are corrupted by white Gaussian noise. We show that the noise-robust R-FFAST algorithm computes a k noise-corrupted time-domain samples in O( k\log ^{4} n) complexity, i.e., sub-linear sample and time complexity. In Section IX, we provide extensive simulation results validating the empirical performance of the R-FFAST algorithm, e.g., we show that the R-FFAST algorithm computes a 50-sparse DFT of an ≈ 10 million length signal using only 4800 noisy samples with an effective signal-to-noise ratio of 5 dB. We also provide comparison of the run-time performance of several existing sparse Fourier transform implementations with that of the R-FFAST and show that it is almost 20 times faster, for comparable settings, than the state-of-the-art algorithm, while simultaneously providing better support recovery guarantees. While our theoretical results are for signals with a uniformly random support of the non-zero DFT coefficients and additive white Gaussian noise, we provide simulation results, which demonstrate that the R-FFAST algorithm performs well even for signals like magnetic resonance images, that have an approximately sparse Fourier spectrum with a non-uniform support for the dominant DFT coefficients. [ABSTRACT FROM PUBLISHER]

Consider a multi-user multi-carrier communication system where multiple users share multiple discrete subcarriers. To achieve high spectrum efficiency, the users in the system must choose their transmit power dynamically in response to fast channel fluctuations. Assuming perfect channel state information, two formulations for the spectrum management (power control) problem are considered in this paper: the first is to minimize the total transmission power subject to all users’ transmission data rate constraints, and the second is to maximize the min-rate utility subject to individual power constraints at each user. It is known in the literature that both formulations of the problem are polynomial time solvable when the number of subcarriers is one and strongly NP-hard when the number of subcarriers are greater than or equal to three. However, the complexity characterization of the problem when the number of subcarriers is two has been missing for a long time. This paper answers this long-standing open question: both formulations of the problem are strongly NP-hard when the number of subcarriers is two. [ABSTRACT FROM PUBLISHER]

In this paper, we design a new iterative low-complexity algorithm for computing the Walsh–Hadamard transform (WHT) of an N dimensional signal with a K -sparse WHT. We suppose that N is a power of two and K=O(N^\alpha) , scales sublinearly in N for some and a computational complexity O(K\log _{2}(K) \log _{2}({N}/{K})) . Moreover, the algorithm succeeds with a high probability approaching 1 for large dimension N . Our approach is mainly based on the subsampling (aliasing) property of the WHT, where by a carefully designed subsampling of the time-domain signal, a suitable aliasing pattern is induced in the transform domain. We treat the resulting aliasing patterns as parity-check constraints and represent them by a bipartite graph. We analyze the properties of the resulting bipartite graphs and borrow ideas from codes defined over sparse bipartite graphs to formulate the recovery of the nonzero spectral values as a peeling decoding algorithm for a specific sparse-graph code transmitted over a binary erasure channel. This enables us to use tools from coding theory (belief-propagation analysis) to characterize the asymptotic performance of our algorithm in the very sparse ( \alpha \in (0, 1/3] ) and the less sparse ( \alpha \in (1/3, 1) ) regime. Comprehensive simulation results are provided to assess the empirical performance of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Sampling from the lattice Gaussian distribution has emerged as an important problem in coding, decoding, and cryptography. In this paper, the classic Metropolis-Hastings (MH) algorithm in Markov chain Monte Carlo methods is adopted for lattice Gaussian sampling. Two MH-based algorithms are proposed, which overcome the limitation of Klein’s algorithm. The first one, referred to as the independent Metropolis-Hastings-Klein (MHK) algorithm, establishes a Markov chain via an independent proposal distribution. We show that the Markov chain arising from this independent MHK algorithm is uniformly ergodic, namely, it converges to the stationary distribution exponentially fast regardless of the initial state. Moreover, the rate of convergence is analyzed in terms of the theta series, leading to predictable mixing time. A symmetric Metropolis-Klein algorithm is also proposed, which is proven to be geometrically ergodic. [ABSTRACT FROM AUTHOR]

The bandwidth of a bandlimited signal is an important number that is relevant in many applications and concepts. For example, according to the Shannon sampling theorem, the bandwidth determines the minimum sampling rate that is required for a perfect reconstruction. In this paper we consider bandlimited signals with finite energy and bandlimited signals that are absolutely integrable and analyze whether the bandwidth of these signals can be determined algorithmically. We employ the concept of Turing computability, a theoretical model that describes the fundamental limits of what can be solved algorithmically on a digital hardware, and ask if, for a given computable bandlimited signal, it is possible to compute its bandwidth on a Turing machine. We show that this is not possible in general, because there exist computable bandlimited signals for which the bandwidth is a non-computable real number. Even the weaker question if the bandwidth of a given signal is smaller than a predefined value cannot be always answered algorithmically. Further, we prove that in the case where the bandwidth in not computable, it is even impossible to algorithmically determine a sequence of upper bounds that converges to the actual bandwidth of the signal. As a positive result, we show that the set of signals whose bandwidth is larger than some given value is semi-decidable. [ABSTRACT FROM AUTHOR]

This paper considers general rank-constrained optimization problems that minimize a general objective function ${f}({X})$ over the set of rectangular ${n}\times {m}$ matrices that have rank at most r. To tackle the rank constraint and also to reduce the computational burden, we factorize $ {X}$ into $ {U} {V} ^{\mathrm {T}}$ where $ {U}$ and $ {V}$ are ${n}\times {r}$ and ${m}\times {r}$ matrices, respectively, and then optimize over the small matrices $ {U}$ and $ {V}$. We characterize the global optimization geometry of the nonconvex factored problem and show that the corresponding objective function satisfies the robust strict saddle property as long as the original objective function f satisfies restricted strong convexity and smoothness properties, ensuring global convergence of many local search algorithms (such as noisy gradient descent) in polynomial time for solving the factored problem. We also provide a comprehensive analysis for the optimization geometry of a matrix factorization problem where we aim to find ${n}\times {r}$ and ${m}\times {r}$ matrices $ {U}$ and $ {V}$ such that $ {U} {V} ^{\mathrm {T}}$ approximates a given matrix $ {X}^\star $. Aside from the robust strict saddle property, we show that the objective function of the matrix factorization problem has no spurious local minima and obeys the strict saddle property not only for the exact-parameterization case where $\mathrm {rank}({X}^\star) = {r}$ , but also for the over-parameterization case where $\mathrm {rank}({X}^\star) < {r}$ and the under-parameterization case where $\mathrm {rank}({X}^\star) > {r}$. These geometric properties imply that a number of iterative optimization algorithms (such as gradient descent) converge to a global solution with random initialization. [ABSTRACT FROM AUTHOR]

In this paper, the problem of developing universal algorithms for noiseless compressed sensing of stochastic processes is studied. First, Rényi’s notion of information dimension (ID) is generalized to continuous-valued discrete-time stationary processes. This provides a measure of complexity for such processes and is connected to the rate of measurement (sampling rate) required for their accurate recovery. Then, based on Occam’s razor, a minimum entropy pursuit (MEP) optimization approach for universal compressed sensing is proposed. It is proven that, for any stationary process satisfying certain mixing conditions, if the sampling rate is larger than the ID of the source process, MEP optimization can reliably recover the source vector almost losslessly, without having any prior information about its distribution. Then, a Lagrangian-type relaxation of MEP optimization problem, referred to as Lagrangian-MEP, is studied. It is shown that Lagrangian-MEP is identical to an implementable algorithm proposed by Baron and coauthors, and for the right choice of parameters, has the same asymptotic performance as MEP optimization. Finally, it is proven that Lagrangian-MEP is robust to small measurement noise. [ABSTRACT FROM AUTHOR]

We consider the problem of recovering a complete (i.e., square and invertible) matrix A0 , from Y \in \mathbb R ^n \times p with Y = A0 X0 , provided X0 is sufficiently sparse. This recovery problem is central to theoretical understanding of dictionary learning, which seeks a sparse representation for a collection of input signals and finds numerous applications in modern signal processing and machine learning. We give the first efficient algorithm that provably recovers A0 when X0 has O \left ( n \right ) nonzeros per column, under suitable probability model for X0 . In contrast, prior results based on efficient algorithms either only guarantee recovery when X0 has O(\sqrt n) zeros per column, or require multiple rounds of semidefinite programming relaxation to work when X0 has $O(n)$ nonzeros per column. Our algorithmic pipeline centers around solving a certain nonconvex optimization problem with a spherical constraint. In this paper, we provide a geometric characterization of the objective landscape. In particular, we show that the problem is highly structured with high probability: 1) there are no “spurious” local minimizers and 2) around all saddle points the objective has a negative directional curvature. This distinctive structure makes the problem amenable to efficient optimization algorithms. In a companion paper, we design a second-order trust-region algorithm over the sphere that provably converges to a local minimizer from arbitrary initializations, despite the presence of saddle points. [ABSTRACT FROM AUTHOR]

We consider the problem of recovering a complete (i.e., square and invertible) matrix A0 , from Y \in \mathbb R ^n \times p with Y = \boldsymbol A0 X0 , provided X0 is sufficiently sparse. This recovery problem is central to theoretical understanding of dictionary learning, which seeks a sparse representation for a collection of input signals and finds numerous applications in modern signal processing and machine learning. We give the first efficient algorithm that provably recovers A0 when X0 has O \left ( n \right ) nonzeros per column, under suitable probability model for X0 . Our algorithmic pipeline centers around solving a certain nonconvex optimization problem with a spherical constraint, and hence is naturally phrased in the language of manifold optimization. In a companion paper, we have showed that with high probability, our nonconvex formulation has no “spurious” local minimizers and around any saddle point, the objective function has a negative directional curvature. In this paper, we take advantage of the particular geometric structure and describe a Riemannian trust region algorithm that provably converges to a local minimizer with from arbitrary initializations. Such minimizers give excellent approximations to the rows of X0 . The rows are then recovered by a linear programming rounding and deflation. [ABSTRACT FROM AUTHOR]

The paper proposes a new message passing algorithm for cycle-free factor graphs. The proposed “entropy message passing” (EMP) algorithm may be viewed as sum-product message passing over the entropy semiring, which has previously appeared in automata theory. The primary use of EMP is to compute the entropy of a model. However, EMP can also be used to compute expressions that appear in expectation maximization and in gradient-descent algorithms. [ABSTRACT FROM AUTHOR]

In the problem of compressed phase retrieval, the goal is to reconstruct a sparse or approximately $k$ -sparse vector $x \in \mathbb {C} ^{n}$ given access to $y= |\Phi x|$ , where $|v|$ denotes the vector obtained from taking the absolute value of $v\in \mathbb {C} ^{n}$ coordinate-wise. In this paper we present sublinear-time algorithms for a few for-each variants of the compressive phase retrieval problem which are akin to the variants considered for the classical compressive sensing problem in theoretical computer science. Our algorithms use pure combinatorial techniques and near-optimal number of measurements. [ABSTRACT FROM AUTHOR]

Phase retrieval refers to algorithmic methods for recovering a signal from its phaseless measurements. There has been recent interest in understanding the performance of local search algorithms that work directly on the non-convex formulation of the problem. Due to the non-convexity of the problem, the success of these local search algorithms depends heavily on their starting points. The most widely used initialization scheme is the spectral method, in which the leading eigenvector of a data-dependent matrix is used as a starting point. Recently, the performance of the spectral initialization was characterized accurately for measurement matrices with independent and identically distributed entries. This paper aims to obtain the same level of knowledge for isotropically random column-orthogonal matrices, which are substantially better models for practical phase retrieval systems. Towards this goal, we consider the asymptotic setting in which the number of measurements $m$ , and the dimension of the signal, $n$ , diverge to infinity with $m/n = \delta \in (1,\infty)$ , and obtain a simple expression for the overlap between the spectral estimator and the true signal vector. [ABSTRACT FROM AUTHOR]

The problem of finding a vector $\boldsymbol {x}$ which obeys a set of quadratic equations $| \boldsymbol {a}_{\text {k}}^\top \boldsymbol {x} |^{2}=\text {y}_{\text {k}}$ , $\text {k}=1,\cdots,\text {m}$ , plays an important role in many applications. In this paper we consider the case when both $\boldsymbol {x}$ and $\boldsymbol {a}_{k}$ are real-valued vectors of length n. A new loss function is constructed for this problem, which combines the smooth quadratic loss function with an activation function. Under the Gaussian measurement model, we establish that with high probability the target solution $\boldsymbol {x}$ is the only minimizer (up to a global sign) of the new loss function provided $\text {m}\gtrsim \text {n}$. Moreover, the loss function always has a negative directional curvature around its saddle points. [ABSTRACT FROM AUTHOR]

In this paper, we consider an exponentially windowed sample covariance matrix (EWSCM) and propose an improved estimator for its eigenvalues. We use new advances in random matrix theory, which describe the limiting spectral distribution of the large dimensional doubly correlated Wishart matrices to find the support and distribution of the eigenvalues of the EWSCM. We then employ the complex integration and residue theorem to design an estimator for the eigenvalues, which satisfies the cluster separability condition, assuming that the eigenvalue multiplicities are known. We show that the proposed estimator is consistent in the asymptotic regime and has good performance in finite sample size situations. Simulation results show that the proposed estimator outperforms the traditional estimator, significantly. [ABSTRACT FROM PUBLISHER]

The standard linear regression (SLR) problem is to recover a vector $\mathrm {x}^{0}$ from noisy linear observations $\mathrm {y}=\mathrm {Ax}^{0}+\mathrm {w}$. The approximate message passing (AMP) algorithm proposed by Donoho, Maleki, and Montanari is a computationally efficient iterative approach to SLR that has a remarkable property: for large i.i.d. sub-Gaussian matrices A, its per-iteration behavior is rigorously characterized by a scalar state-evolution whose fixed points, when unique, are Bayes optimal. The AMP algorithm, however, is fragile in that even small deviations from the i.i.d. sub-Gaussian model can cause the algorithm to diverge. This paper considers a “vector AMP” (VAMP) algorithm and shows that VAMP has a rigorous scalar state-evolution that holds under a much broader class of large random matrices A: those that are right-orthogonally invariant. After performing an initial singular value decomposition (SVD) of A, the per-iteration complexity of VAMP is similar to that of AMP. In addition, the fixed points of VAMP’s state evolution are consistent with the replica prediction of the minimum mean-squared error derived by Tulino, Caire, Verdú, and Shamai. Numerical experiments are used to confirm the effectiveness of VAMP and its consistency with state-evolution predictions. [ABSTRACT FROM AUTHOR]

We consider the nonadaptive group testing with $N$ items, of which $K = \Theta (N^\theta)$ are defective. We study a test design in which each item appears in nearly the same number of tests. For each item, we independently pick $L$ tests uniformly at random with replacement and place the item in those tests. We analyze the performance of these designs with simple and practical decoding algorithms in a range of sparsity regimes and show that the performance is consistently improved in comparison with standard Bernoulli designs. We show that our new design requires roughly 23% fewer tests than a Bernoulli design when paired with the simple decoding algorithms known as combinatorial orthogonal matching pursuit and definite defectives (DD). This gives the best known nonadaptive group testing performance for $\theta > 0.43$ and the best proven performance with a practical decoding algorithm for all $\theta \in (0,1)$. We also give a converse result showing that the DD algorithm is optimal with respect to our randomized design when $\theta > 1/2$. We complement our theoretical results with simulations that show a notable improvement over Bernoulli designs in both sparse and dense regimes. [ABSTRACT FROM AUTHOR]

We consider the classical problem of finding the sparse representation of a signal in a pair of bases. When both bases are orthogonal, it is known that the sparse representation is unique when the sparsity K of the signal satisfies K<1/\mu ( {\boldsymbol {D}}) , where \mu ( {\boldsymbol {D}}) is the mutual coherence of the dictionary. Furthermore, the sparse representation can be obtained in polynomial time by basis pursuit (BP), when K<0.91/\mu ( \boldsymbol D) . Therefore, there is a gap between the unicity condition and the one required to use the polynomial-complexity BP formulation. For the case of general dictionaries, it is also well known that finding the sparse representation under the only constraint of unicity is NP-hard. In this paper, we introduce, for the case of Fourier and canonical bases, a polynomial complexity algorithm that finds all the possible K -sparse representations of a signal under the weaker condition that K<\sqrt 2 /\mu ( \boldsymbol D) . Consequently, when K<1/\mu ( \boldsymbol D) , the proposed algorithm solves the unique sparse representation problem for this structured dictionary in polynomial time. We further show that the same method can be extended to many other pairs of bases, one of which must have local atoms. Examples include the union of Fourier and local Fourier bases, the union of discrete cosine transform and canonical bases, and the union of random Gaussian and canonical bases. [ABSTRACT FROM PUBLISHER]

The computation of the sparse principal component of a matrix is equivalent to the identification of its principal submatrix with the largest maximum eigenvalue. Finding this optimal submatrix is what renders the problem \cal NP-hard. In this paper, we prove that, if the matrix is positive semidefinite and its rank is constant, then its sparse principal component is polynomially computable. Our proof utilizes the auxiliary unit vector technique that has been recently developed to identify problems that are polynomially solvable. In addition, we use this technique to design an algorithm which, for any sparsity value, computes the sparse principal component with complexity \cal O(N^D+1), where N and D are the matrix size and rank, respectively. Our algorithm is fully parallelizable and memory efficient. [ABSTRACT FROM PUBLISHER]

We consider the multichannel blind deconvolution problem where we observe the output of multiple channels that are all excited with the same unknown input. From these observations, we wish to estimate the impulse responses of each of the channels. We show that this problem is well-posed if the channels follow a bilinear model where the ensemble of channel responses is modeled as lying in a low-dimensional subspace but with each channel modulated by an independent gain. Under this model, we show how the channel estimates can be found by minimizing a quadratic function over a non-convex set. We analyze two methods for solving this non-convex program, and provide performance guarantees for each. The first is a method of alternating eigenvectors that breaks the program down into a series of eigenvalue problems. The second is a truncated power iteration, which can roughly be interpreted as a method for finding the largest eigenvector of a symmetric matrix with the additional constraint that it adheres to our bilinear model. As with most non-convex optimization algorithms, the performance of both of these algorithms is highly dependent on having a good starting point. We show how such a starting point can be constructed from the channel measurements. Our performance guarantees are non-asymptotic, and provide a sufficient condition on the number of samples observed per channel in order to guarantee channel estimates of certain accuracy. Our analysis uses a model with a “generic” subspace that is drawn at random, and we show the performance bounds hold with high probability. Mathematically, the key estimates are derived by quantifying how well the eigenvectors of certain random matrices approximate the eigenvectors of their mean. We also present a series of numerical results demonstrating that the empirical performance is consistent with the presented theory. [ABSTRACT FROM AUTHOR]

In the framework of prediction of individual sequences, sequential prediction methods are to be constructed that perform nearly as well as the best expert from a given class. We consider prediction strategies that compete with the class of switching strategies that can segment a given sequence into several blocks, and follow the advice of a different “base” expert in each block. As usual, the performance of the algorithm is measured by the regret defined as the excess loss relative to the best switching strategy selected in hindsight for the particular sequence to be predicted. In this paper, we construct prediction strategies of low computational cost for the case where the set of base experts is large. In particular, we provide a method that can transform any prediction algorithm \cal A that is designed for the base class into a tracking algorithm. The resulting tracking algorithm can take advantage of the prediction performance and potential computational efficiency of \cal A in the sense that it can be implemented with time and space complexity only O(n^\gamma \ln n) times larger than that of \cal A, where n is the time horizon and \gamma \geq 0 is a parameter of the algorithm. With \cal A properly chosen, our algorithm achieves a regret bound of optimal order for \gamma > 0, and only O(\ln n) times larger than the optimal order for \gamma =0 for all typical regret bound types we examined. For example, for predicting binary sequences with switching parameters under the logarithmic loss, our method achieves the optimal O(\ln n) regret rate with time complexity O(n^1+\gamma \ln n) for any \gamma \in (0,1). [ABSTRACT FROM PUBLISHER]

We consider the orthogonal matching pursuit (OMP) algorithm for the recovery of a high-dimensional sparse signal based on a small number of noisy linear measurements. OMP is an iterative greedy algorithm that selects at each step the column, which is most correlated with the current residuals. In this paper, we present a fully data driven OMP algorithm with explicit stopping rules. It is shown that under conditions on the mutual incoherence and the minimum magnitude of the nonzero components of the signal, the support of the signal can be recovered exactly by the OMP algorithm with high probability. In addition, we also consider the problem of identifying significant components in the case where some of the nonzero components are possibly small. It is shown that in this case the OMP algorithm will still select all the significant components before possibly selecting incorrect ones. Moreover, with modified stopping rules, the OMP algorithm can ensure that no zero components are selected. [ABSTRACT FROM AUTHOR]

We consider the high-dimensional linear regression problem, where the algorithmic goal is to efficiently infer an unknown feature vector $\beta ^{*}\in \mathbb {R}^{p}$ from its linear measurements, using a small number $n$ of samples. Unlike most of the literature, we make no sparsity assumption on $\beta ^{*}$ , but instead adopt a different regularization: In the noiseless setting, we assume $\beta ^{*}$ consists of entries, which are either rational numbers with a common denominator $Q\in \mathbb {Z}^{+}$ (referred to as $Q-$ rationality); or irrational numbers taking values in a rationally independent set of bounded cardinality, known to learner; collectively called as the mixed-range assumption. Using a novel combination of the Partial Sum of Least Squares (PSLQ) integer relation detection, and the Lenstra-Lenstra-Lovász (LLL) lattice basis reduction algorithms, we propose a polynomial-time algorithm which provably recovers a $\beta ^{*}\in \mathbb {R}^{p}$ enjoying the mixed-range assumption, from its linear measurements $Y=X\beta ^{*}\in \mathbb {R}^{n}$ for a large class of distributions for the random entries of $X$ , even with one measurement ($n=1$). In the noisy setting, we propose a polynomial-time, lattice-based algorithm, which recovers a $\beta ^{*}\in \mathbb {R}^{p}$ enjoying the $Q-$ rationality property, from its noisy measurements $Y=X\beta ^{*}+W\in \mathbb {R}^{n}$ , even from a single sample ($n=1$). We further establish that for large $Q$ , and normal noise, this algorithm tolerates information-theoretically optimal level of noise. We then apply these ideas to develop a polynomial-time, single-sample algorithm for the phase retrieval problem. Our methods address the single-sample ($n=1$) regime, where the sparsity-based methods such as the Least Absolute Shrinkage and Selection Operator (LASSO) and the Basis Pursuit are known to fail. Furthermore, our results also reveal algorithmic connections between the high-dimensional linear regression problem, and the integer relation detection, randomized subset-sum, and shortest vector problems. [ABSTRACT FROM AUTHOR]

The nonlinear characteristic in a Hammerstein system, i.e., a system in which a nonlinear memoryless subsystem and a linear dynamic are connected in a cascade, is recovered with the nonparametric nearest neighbor regression estimate. The a priori information is nonparametric, both the nonlinear characteristic and the impulse response are completely unknown and can be of any form. Local and global properties of the estimate are examined. Whatever the probability density of the input signal, the estimate converges at every continuity point of the characteristic as well as in the global sense. We derive the asymptotic bias and variance of the proposed estimate. As a result, the optimal rate of convergence is established that additionally is independent of the shape of the input density. Results of numerical simulations are also presented. [ABSTRACT FROM AUTHOR]

A denoising algorithm seeks to remove noise, errors, or perturbations from a signal. Extensive research has been devoted to this arena over the last several decades, and as a result, todays denoisers can effectively remove large amounts of additive white Gaussian noise. A compressed sensing (CS) reconstruction algorithm seeks to recover a structured signal acquired using a small number of randomized measurements. Typical CS reconstruction algorithms can be cast as iteratively estimating a signal from a perturbed observation. This paper answers a natural question: How can one effectively employ a generic denoiser in a CS reconstruction algorithm? In response, we develop an extension of the approximate message passing (AMP) framework, called denoising-based AMP (D-AMP), that can integrate a wide class of denoisers within its iterations. We demonstrate that, when used with a high-performance denoiser for natural images, D-AMP offers the state-of-the-art CS recovery performance while operating tens of times faster than competing methods. We explain the exceptional performance of D-AMP by analyzing some of its theoretical features. A key element in D-AMP is the use of an appropriate Onsager correction term in its iterations, which coerces the signal perturbation at each iteration to be very close to the white Gaussian noise that denoisers are typically designed to remove. [ABSTRACT FROM PUBLISHER]

The problem of quickest detection of dynamic events in networks is studied. At some unknown time, an event occurs, and a number of nodes in the network are affected by the event, in that they undergo a change in the statistics of their observations. It is assumed that the event is dynamic, in that it can propagate along the edges in the network, and affect more and more nodes with time. The event propagation dynamics is assumed to be unknown. The goal is to design a sequential algorithm that can detect a “significant” event, i.e., when the event has affected no fewer than $\eta $ nodes, as quickly as possible, while controlling the false alarm rate. Fully connected networks are studied first, and the results are then extended to arbitrarily connected networks. The designed algorithms are shown to be adaptive to the unknown propagation dynamics, and their first-order asymptotic optimality is demonstrated as the false alarm rate goes to zero. The algorithms can be implemented with linear computational complexity in the network size at each time step, which is critical for online implementation. Numerical simulations are provided to validate the theoretical results. [ABSTRACT FROM AUTHOR]

This paper revisits the sparse multiple measurement vector (MMV) problem, where the aim is to recover a set of jointly sparse multichannel vectors from incomplete measurements. This problem is an extension of single channel sparse recovery, which lies at the heart of compressed sensing. Inspired by the links to array signal processing, a new family of MMV algorithms is considered that highlight the role of rank in determining the difficulty of the MMV recovery problem. The simplest such method is a discrete version of MUSIC which is guaranteed to recover the sparse vectors in the full rank MMV setting, under mild conditions. This idea is extended to a rank aware pursuit algorithm that naturally reduces to Order Recursive Matching Pursuit (ORMP) in the single measurement case while also providing guaranteed recovery in the full rank setting. In contrast, popular MMV methods such as Simultaneous Orthogonal Matching Pursuit (SOMP) and mixed norm minimization techniques are shown to be rank blind in terms of worst case analysis. Numerical simulations demonstrate that the rank aware techniques are significantly better than existing methods in dealing with multiple measurements. [ABSTRACT FROM AUTHOR]

We investigate the fundamental conditions on the sampling pattern, i.e., locations of the sampled entries, for finite completability of a low-rank tensor given some components of its Tucker rank. In order to find the deterministic necessary and sufficient conditions, we propose an algebraic geometric analysis on the Tucker manifold, which allows us to incorporate multiple rank components in the proposed analysis in contrast with the conventional geometric approaches on the Grassmannian manifold. This analysis characterizes the algebraic independence of a set of polynomials defined based on the sampling pattern, which is closely related to finite completability of the sampled tensor, where finite completability simply means that the number of possible completions of the sampled tensor is finite. Probabilistic conditions are then studied and a lower bound on the sampling probability is given, which guarantees that the proposed deterministic conditions on the sampling patterns for finite completability hold with high probability. Furthermore, using the proposed geometric approach for finite completability, we propose a sufficient condition on the sampling pattern that ensures there exists exactly one completion of the sampled tensor. [ABSTRACT FROM AUTHOR]

The problem of recovering a one-dimensional signal from its Fourier transform magnitude, called Fourier phase retrieval, is ill-posed in most cases. We consider the closely-related problem of recovering a signal from its phaseless short-time Fourier transform (STFT) measurements. This problem arises naturally in several applications, such as ultra-short laser pulse characterization and ptychography. The redundancy offered by the STFT enables unique recovery under mild conditions. We show that in some cases the unique solution can be obtained by the principal eigenvector of a matrix, constructed as the solution of a simple least-squares problem. When these conditions are not met, we suggest using the principal eigenvector of this matrix to initialize non-convex local optimization algorithms and propose two such methods. The first is based on minimizing the empirical risk loss function, while the second maximizes a quadratic function on the manifold of phases. We prove that under appropriate conditions, the proposed initialization is close to the underlying signal. We then analyze the geometry of the empirical risk loss function and show numerically that both gradient algorithms converge to the underlying signal even with small redundancy in the measurements. In addition, the algorithms are robust to noise. [ABSTRACT FROM PUBLISHER]

Motivated by recent work on stochastic gradient descent methods, we develop two stochastic variants of greedy algorithms for possibly non-convex optimization problems with sparsity constraints. We prove linear convergence1 in expectation to the solution within a specified tolerance. This generalized framework is specialized to the problems of sparse signal recovery in compressed sensing and low-rank matrix recovery, giving methods with provable convergence guarantees that often outperform their deterministic counterparts. We also analyze the settings, where gradients and projections can only be computed approximately, and prove the methods are robust to these approximations. We include many numerical experiments, which align with the theoretical analysis and demonstrate these improvements in several different settings.1

Linear convergence is sometimes called exponential convergence.

Binary measurements arise naturally in a variety of statistics and engineering applications. They may be inherent to the problem—for example, in determining the relationship between genetics and the presence or absence of a disease—or they may be a result of extreme quantization. A recent influx of literature has suggested that using prior signal information can greatly improve the ability to reconstruct a signal from binary measurements. This is exemplified by one-bit compressed sensing, which takes the compressed sensing model but assumes that only the sign of each measurement is retained. It has recently been shown that the number of one-bit measurements required for signal estimation mirrors that of unquantized compressed sensing. Indeed, s -sparse signals in {\mathbb R}^{n} can be estimated (up to normalization) from \Omega (s \log ~(n/s))$ one-bit measurements. Nevertheless, controlling the precise accuracy of the error estimate remains an open challenge. In this paper, we focus on optimizing the decay of the error as a function of the oversampling factor \lambda := m/(s \log (n/s))$ , where m$ is the number of measurements. It is known that the error in reconstructing sparse signals from standard one-bit measurements is bounded below by . Without adjusting the measurement procedure, reducing this polynomial error decay rate is impossible. However, we show that an adaptive choice of the thresholds used for quantization can lower the error rate to e^{-\Omega (\lambda )} . This improves upon guarantees for other methods of adaptive thresholding, such as sigma–delta quantization. We develop a general recursive strategy to achieve this exponential decay and two specific polynomial-time algorithms, which fall into this framework, one based on convex programming and one on hard thresholding. Our work bridges the one-bit compressed sensing model, in which the engineer controls the measurement procedure, to sigma–delta and successive approximation quantization. Moreover, the principle is extendable to signal reconstruction problems in a variety of binary statistical models as well as statistical estimation problems like logistic regression. [ABSTRACT FROM AUTHOR]

For almost-cyclostationary processes, sufficient conditions are derived, such that estimates of the second-order cyclic probabilistic functions with estimated cycle frequencies are mean-square consistent and asymptotically complex normal. Cyclic (conjugate) autocorrelation functions and cyclic (conjugate) spectra are considered. Under the derived conditions, asymptotically, as the data-record length approaches infinity, the estimates of cyclic statistics with estimated cycle frequencies have the same complex normal distribution as the case of exactly known cycle frequencies. The results are applied to the detection of a moving cyclostationary source in the presence of strong Doppler effect and for low values of SNR. [ABSTRACT FROM PUBLISHER]

As constructing multi-D wavelets remains a challenging problem, we propose a new method called prime coset sum to construct multi-D wavelets. Our method provides a systematic way to construct multi-D non-separable wavelet filter banks from two 1-D low-pass filters, with one of which being interpolatory. Our method has many important features including the following: 1) it works for any spatial dimension, and any prime scalar dilation; 2) the vanishing moments of the multi-D wavelet filter banks are guaranteed by certain properties of the initial 1-D low-pass filters, and furthermore; 3) the resulting multi-D wavelet filter banks are associated with fast algorithms that are faster than the existing fast tensor product algorithms. [ABSTRACT FROM PUBLISHER]

We study the problem of mismatched binary hypothesis testing between i.i.d. distributions. We analyze the tradeoff between the pairwise error probability exponents when the actual distributions generating the observation are different from the distributions used in the likelihood ratio test, sequential probability ratio test, and Hoeffding’s generalized likelihood ratio test in the composite setting. When the real distributions are within a small divergence ball of the test distributions, we find the deviation of the worst-case error exponent of each test with respect to the matched error exponent. In addition, we consider the case where an adversary tampers with the observation, again within a divergence ball of the observation type. We show that the tests are more sensitive to distribution mismatch than to adversarial observation tampering. [ABSTRACT FROM AUTHOR]

Matroidal networks were introduced by Dougherty et al. and have been well studied in the recent past. It was shown that a network has a scalar linear network coding solution if and only if it is matroidal associated with a representable matroid. A particularly interesting feature of this development is the ability to construct (scalar and vector) linearly solvable networks using certain classes of matroids. Furthermore, it was shown through the connection between network coding and matroid theory that linear network coding is not always sufficient for general network coding scenarios. The current work attempts to establish a connection between matroid theory and network-error correcting and detecting codes. In a similar vein to the theory connecting matroids and network coding, we abstract the essential aspects of linear network-error detecting codes to arrive at the definition of a matroidal error detecting network (and similarly, a matroidal error correcting network abstracting from network-error correcting codes). An acyclic network (with arbitrary sink demands) is then shown to possess a scalar linear error detecting (correcting) network code if and only if it is a matroidal error detecting (correcting) network associated with a representable matroid. Therefore, constructing such network-error correcting and detecting codes implies the construction of certain representable matroids that satisfy some special conditions, and vice versa. We then present algorithms that enable the construction of matroidal error detecting and correcting networks with a specified capability of network-error correction. Using these construction algorithms, a large class of hitherto unknown scalar linearly solvable networks with multisource, multicast, and multiple-unicast network-error correcting codes is made available for theoretical use and practical implementation, with parameters, such as number of information symbols, number of sinks, number of coding nodes, error correcting capability, and so on, being arbitrary but for computing power (for the execution of the algorithms). The complexity of the construction of these networks is shown to be comparable with the complexity of existing algorithms that design multicast scalar linear network-error correcting codes. Finally, we also show that linear network coding is not sufficient for the general network-error correction (detection) problem with arbitrary demands. In particular, for the same number of network errors, we show a network for which there is a nonlinear network-error detecting code satisfying the demands at the sinks, whereas there are no linear network-error detecting codes that do the same. [ABSTRACT FROM AUTHOR]

We present a deterministic algorithm for finding the significant Fourier frequencies of a given signal f\in\BBC^N and their approximate Fourier coefficients in running time and sample complexity polynomial in \log N, L1(\widehat f)/\Vert\widehat f\Vert2, and 1/\tau, where the significant frequencies are those occupying at least a \tau-fraction of the energy of the signal, and L1(\widehat f) denotes the L1-norm of the Fourier transform of f. Furthermore, the algorithm is robust to additive random noise. This strictly extends the class of compressible/Fourier sparse signals efficiently handled by previous deterministic algorithms for signals in \BBC^N. As a central tool, we prove there is a deterministic algorithm that takes as input N, \varepsilon and an arithmetic progression P in \BBZN, runs in time polynomial in \ln N and 1/\varepsilon, and returns a set AP that \varepsilon-approximates P in \BBZN in the sense that \vert\mathop\BBEx\in APe^{2\pi i\omega x/N}-\mathop\BBEx\in Pe^{2\pi i\omega x/N}\vert <\varepsilon for all \omega=0,\ldots, N-1. In other words, we show there is an explicit construction of sets AP of size polynomial in \ln N and 1/\varepsilon that \varepsilon-approximate given arithmetic progressions P in \BBZN. This extends results on small-bias sets, which are sets approximating the entire domain, to sets approximating a given arithmetic progression; this result may be of independent interest. [ABSTRACT FROM PUBLISHER]

Graph convolutional networks (GCNs) are a widely used method for graph representation learning. To elucidate their capabilities and limitations for graph classification, we investigate their power to generate well-separated embedding vectors for graphs sampled from different random graph models, which correspond to different class-conditional distributions in a classification problem. It has been recognized that metric properties of learned representations are important for reduction of complexity of classifiers trained on them. Additionally, we show that inability to generate well-separated embedding vectors for two different graph models implies information-theoretic indistinguishability of these models based on noise-perturbed embedding vectors of sample graphs. We consider graph models arising from graphons, which parametrize all infinite exchangeable graph models. We precisely characterize, in terms of degree profile closeness, the set of graphon pairs that are indistinguishable (in metric and information-theoretic senses) by a GCN with depth at least logarithmic in sample graph size. Outside this set, a very simple architecture suffices for distinguishability. We then exhibit a concrete, infinite set of graphon pairs that are well-separated in cut distance and are indistinguishable by a GCN. These results theoretically match empirical observations of several prior works. Finally, we give empirical results on synthetic and real graph classification datasets, giving some indication that degree profile closeness gives rise to indistinguishability of graph distributions in real datasets, even beyond our theoretical framework. [ABSTRACT FROM AUTHOR]

An indel refers to a single insertion or deletion, while an edit refers to a single insertion, deletion or substitution. In this article, we investigate codes that correct either a single indel or a single edit and provide linear-time algorithms that encode binary messages into these codes of length n. Over the quaternary alphabet, we provide two linear-time encoders. One corrects a single edit with ⌈log n⌉ + O(log log n) redundancy bits, while the other corrects a single indel with ⌈log n⌉ + 2 redundant bits. These two encoders are order-optimal. The former encoder is the first known order-optimal encoder that corrects a single edit, while the latter encoder (that corrects a single indel) reduces the redundancy of the best known encoder of Tenengolts (1984) by at least four bits. Over the DNA alphabet, we impose an additional constraint: the GC-balanced constraint and require that exactly half of the symbols of any DNA codeword to be either C or G. In particular, via a modification of Knuth’s balancing technique, we provide a linear-time map that translates binary messages into GC-balanced codewords and the resulting codebook is able to correct a single indel or a single edit. These are the first known constructions of GC-balanced codes that correct a single indel or a single edit. [ABSTRACT FROM AUTHOR]

In this article, the concept and definitions of the Fractional Order Moment (FOM) and Fractional Order Cumulant (FOC) are proposed, which is based on the fractional derivative of the fractional order Moment-generating function and the fractional order Cumulant-generating function of stochastic processes. The moment and cumulant are defined on an expanded set from positive integer to the whole positive real. This development not only provides a new technology for signal processing, also complements the existing theory in the field. The properties of the FOC have been derived, and their uniformity and particularity with the High Order Cumulant are compared and commented. In addition, the transformation between the FOM and the FOC are derived and discussed in detail. As one of the applications of the new concept to the $\alpha $ and Gaussian processes, a new method of suppressing $\alpha $ and Gaussian noise is proposed. Furthermore, a FOC-based parameter estimation algorithm is developed for the non-minimum phase ARMA processes in $\alpha $ and/or Gaussian noise. Simulation examples are used to demonstrate the effectiveness of the proposed parameter estimation algorithm. [ABSTRACT FROM AUTHOR]

We investigate the statistical and algorithmic properties of random neural-network generative priors in a simple inference problem: spiked-matrix estimation. We establish a rigorous expression for the performance of the Bayes-optimal estimator in the high-dimensional regime, and identify the statistical threshold for weak-recovery of the spike. Next, we derive a message-passing algorithm taking into account the latent structure of the spike, and show that its performance is asymptotically optimal for natural choices of the generative network architecture. The absence of an algorithmic gap in this case is in stark contrast to known results for sparse spikes, another popular prior for modelling low-dimensional signals, and for which no algorithm is known to achieve the optimal statistical threshold. Finally, we show that linearising our message passing algorithm yields a simple spectral method also achieving the optimal threshold for reconstruction. We conclude with an experiment on a real data set showing that our bespoke spectral method outperforms vanilla PCA. [ABSTRACT FROM AUTHOR]