Compressed sensing, which involves reconstruction of sparse signals from an under-determined linear system, has been recently applied to problems in group testing to save on the number of tests administered during a pandemic or other resource-constrained scenarios. In practical group testing in time-constrained situations, the results of two different groups can sometimes be mistakenly exchanged by a technician. This is called ‘permutation noise’ and it presents challenges in determining the signal vector containing p health status values of the participating subjects from the results on n ≪ p pooled tests. In this paper, we present a method to determine the health status values in a manner that is robust to a small number of such permutations. The technique is based on a ‘debiased’ form of the robust LASSO estimator, with which we carefully design hypothesis tests in order (i) to identify the unhealthy subjects (based on non-zero values in the health status signal vector), and (ii) to identify the pooled measurements which were corrupted by permutation noise. Furthermore, we present an algorithm to correct the permutations in the pooled tests and subsequently reconstruct the signal vector from the corrected measurements. We further provide empirical results showing the efficacy of both the identification and correction of permutation errors, and show that it is superior to many intuitive baseline techniques.

Channels with noisy duplications have recently been used to model the nanopore sequencer. This paper extends some foundational information-theoretic results to this new scenario. We prove the asymptotic equipartition property (AEP) for noisy duplication processes based on ergodic Markov processes. A consequence is that the noisy duplication channel is information stable for ergodic Markov sources, and therefore the channel capacity constrained to Markov sources is the Markov -constrained Shannon capacity. We use the AEP to estimate lower bounds on the capacity of the binary symmetric channel with Bernoulli and geometric duplications using Monte Carlo simulations. In addition, we relate the AEP for noisy duplication processes to the AEP for hidden semi-Markov processes.

The Blahut-Arimoto algorithm is a well-known method to compute classical channel capacities and rate-distortion functions. Recent works have extended this algorithm to compute various quantum analogs of these quantities. In this paper, we show how these Blahut-Arimoto algorithms are special instances of mirror descent, which is a type of Bregman proximal method, and a well-studied generalization of gradient descent for constrained convex optimization. Using recently developed convex analysis tools, we show how analysis based on relative smoothness and strong convexity recovers known sublinear and linear convergence rates for Blahut-Arimoto algorithms. This Bregman proximal viewpoint allows us to derive related algorithms with similar convergence guarantees to solve problems in information theory for which Blahut-Arimoto-type algorithms are not directly applicable. We apply this framework to compute energy-constrained classical and quantum channel capacities, classical and quantum rate-distortion functions, and approximations of the relative entropy of entanglement, all with provable convergence guarantees.

The noisy nanopore channel is introduced as a model of the nanopore sequencer in DNA storage that includes inter-symbol interference, sample duplications, and measurement noise. Information rates of the noisy nanopore channel with Markov sources are computed numerically based on a Monte Carlo technique that builds upon existing techniques for finite-state channels. However, the analogous technique for channels with duplications poses a challenging problem from an algorithmic perspective. An approximate algorithm is proposed to compute information rates inO(m√mlog(m)) time with an asymptotically negligible error with respect to block lengthm. Information rates of the nanopore sequencer are studied by choosing parameters of the channel model based on the Scrappie simulator, yielding insights into the fundamental performance of DNA storage systems with nanopore sequencing as the reading process.

The difference of convex (DC) algorithm is a conceptually simple method for the minimization of (non)convex functions that are expressed as the difference of two convex functions. An attractive feature of the algorithm is that it maintains a global overestimator on the function and does not require a choice of step size at each iteration. By adopting a Bregman divergence point of view, we simplify and strengthen many existing non-asymptotic convergence guarantees for the DC algorithm. We further present several sufficient conditions that ensure a linear convergence rate, namely a new DC Polyak-Lojasiewicz condition, as well as a relative strong convexity assumption. Importantly, our conditions do not require smoothness of the objective function. We illustrate our results on a family of minimization problems involving the quantum relative entropy, with applications in quantum information theory.

We consider the problem of solving large-scale instances of the Max-Cut semidefinite program (SDP), i.e., optimizing a linear function over $n\times n$ positive semidefinite (PSD) matrices with unit diagonal. When the cost matrix is PSD, we show how to exactly reformulate the problem as maximizing a smooth concave function over PSD matrices with unit trace. By applying the Frank-Wolfe method, we obtain a simple algorithm that is compatible with recent sampling-based techniques to solve SDPs using low memory. We demonstrate the practical performance of our method on $10^6\times 10^6$ instances of the max-cut SDP with costs having up to $5 \times 10^6$ non-zero entries. Theoretically, we show that our method solves problems with diagonally dominant costs to relative error $\epsilon$ in $O(n\epsilon^{-1})$ calls to a randomized approximate largest eigenvalue subroutine, each of which succeeds with high probability after $O(\log(n)\epsilon^{-1/2})$ matrix-vector multiplications with the cost matrix.

This paper considers coding schemes for the noisy nanopore channel that models the nanopore sequencer in DNA storage. Our approach involves designing a target Markov source subject to general source constraints, including the homopolymer run-length and GC constraints. We propose a concatenated coding scheme with an inner homophonic code and generic outer error-correction code. The inner code maps binary i.i.d. sources to the target quaternary Markov source by minimising error in the empirical Markov distribution, which measures its "Markov-like" behaviour. This leads to the proposed low-complexity, near-optimal soft decoder for the inner code, demonstrated through numerical results.

Nanopore sequencing is an emerging DNA sequencing technology that has been proposed for use in DNA storage systems. We propose the noisy nanopore channel model for nanopore sequencing. This model captures duplications, inter-symbol interference, and noisy measurements by concatenating an i.i.d. duplication channel with a finite-state semi-Markov channel. Compared to previous models, this channel models the dominant distortions of the nanopore while remaining tractable. Anticipating future coding schemes, we derive MAP detection algorithms and estimate achievable rates. Given that finite-state semi-Markov channels are a subclass of channels with memory, we conjecture that the achievable rate of the noisy nanopore channel can be optimised using a variation of the generalised Blahut-Arimoto algorithm.

Max-k-Cut and correlation clustering are fundamental graph partitioning problems. For a graph $G=(V,E)$ with $n$ vertices, the methods with the best approximation guarantees for Max-k-Cut and the Max-Agree variant of correlation clustering involve solving SDPs with $\mathcal{O}(n^2)$ constraints and variables. Large-scale instances of SDPs, thus, present a memory bottleneck. In this paper, we develop simple polynomial-time Gaussian sampling-based algorithms for these two problems that use $\mathcal{O}(n+|E|)$ memory and nearly achieve the best existing approximation guarantees. For dense graphs arriving in a stream, we eliminate the dependence on $|E|$ in the storage complexity at the cost of a slightly worse approximation ratio by combining our approach with sparsification.

We analyze an estimator based on the Bregman divergence for recovery of structured models from additive noise. The estimator can be seen as a regularized maximum likelihood estimator for an exponential family where the natural parameter is assumed to be structured. For all such Bregman denoising estimators, we provide an error bound for a natural associated error measure. Our error bound makes it possible to analyze a wide range of estimators, such as those in proximal denoising and inverse covariance matrix estimation, in a unified manner. In the case of proximal denoising, we exactly recover the existing tight normalized mean squared error bounds. In sparse precision matrix estimation, our bounds provide optimal scaling with interpretable constants in terms of the associated error measure.

Phaseless super-resolution is the problem of reconstructing a signal from its low-frequency Fourier magnitude measurements. It is the combination of two classic signal processing problems: phase retrieval and super-resolution. Due to the absence of phase and high-frequency measurements, additional information is required in order to be able to uniquely reconstruct the signal of interest. In this work, we use masks to introduce redundancy in the phaseless measurements. We develop an analysis framework for this setup, and use it to show that any super-resolution algorithm can be seamlessly extended to solve phaseless superresolution (up to a global phase), when measurements are obtained using a certain set of masks. In particular, we focus our attention on a robust semidefinite relaxation-based algorithm, and provide reconstruction guarantees. Numerical simulations complement our theoretical analysis.

Let X* be a n1× n2matrix with entries in F2and rank r1, n2) (often r ≪ min(n1, n2)). We consider the problem of reconstructing X* given only a subset of its entries. This problem has recently found numerous applications, most notably in network and index coding, where finding optimal linear codes (over some field Fq) can be reduced to finding the minimum rank completion of a matrix with a subset of revealed entries. The problem of matrix completion over reals also has many applications and in recent years several polynomial-time algorithms with provable recovery guarantees have been developed. However, to date, such algorithms do not exist in the finite-field case. We propose a linear algebraic algorithm, based on inferring low-weight relations among the rows and columns of X*, to attempt to complete X* given a random subset of its entries. We establish conditions on the row and column spaces of X* under which the algorithm runs in polynomial time (in the size of X*) and can successfully complete X* with high probability from a vanishing fraction of its entries. We then propose a linear programming-based extension of our basic algorithm, and evaluate it empirically.

Sampling inference methods are computationally difficult to scale for many models in part because global dependencies can reduce opportunities for parallel computation. Without strict conditional independence structure among variables, standard Gibbs sampling theory requires sample updates to be performed sequentially, even if dependence between most variables is not strong. Empirical work has shown that some models can be sampled effectively by going Hogwild'' and simply running Gibbs updates in parallel with only periodic global communication, but the successes and limitations of such a strategy are not well understood. As a step towards such an understanding, we study the Hogwild Gibbs sampling strategy in the context of Gaussian distributions. We develop a framework which provides convergence conditions and error bounds along with simple proofs and connections to methods in numerical linear algebra. In particular, we show that if the Gaussian precision matrix is generalized diagonally dominant, then any Hogwild Gibbs sampler, with any update schedule or allocation of variables to processors, yields a stable sampling process with the correct sample mean. "

Clustering with advice (often known as constrained clustering) has been a recent focus of the data mining community. Success has been achieved incorporating advice into the k-means and spectral clustering frameworks. Although the theory community has explored inconsistent advice, it has not yet been incorporated into spectral clustering. Extending work of De Bie and Cristianini, we set out a framework for finding minimum normalised cuts, subject to inconsistent advice.