Junren Chen

Junren Chen, Michael K. Ng, Jonathan Scarlett

Phase-only compressed sensing (PO-CS) concerns the recovery of sparse signals from the phases of complex measurements. Recent results show that sparse signals in the standard sphere $\mathbb{S}^{n-1}$ can be exactly recovered from complex Gaussian phases by a linearization procedure, which recasts PO-CS as linear compressed sensing and then applies (quadratically constrained) basis pursuit to obtain $\mathbf{x}^\sharp$. This paper focuses on the instance optimality and robustness of $\mathbf{x}^{\sharp}$. First, we strengthen the nonuniform instance optimality of Jacques and Feuillen (2021) to a uniform one over the entire signal space. We show the existence of some universal constant $C$ such that $\|\mathbf{x}^\sharp-\mathbf{x}\|_2\le Cs^{-1/2}σ_{\ell_1}(\mathbf{x},Σ^n_s)$ holds for all $\mathbf{x}$ in the unit Euclidean sphere, where $σ_{\ell_1}(\mathbf{x},Σ^n_s)$ is the $\ell_1$ distance of $\mathbf{x}$ to its closest $s$-sparse signal. This is achieved by showing the new sensing matrices corresponding to all approximately sparse signals simultaneously satisfy RIP. Second, we investigate the estimator's robustness to noise and corruption. We show that dense noise with entries bounded by some small $τ_0$, appearing either prior or posterior to retaining the phases, increments $\|\mathbf{x}^\sharp-\mathbf{x}\|_2$ by $O(τ_0)$. This is near-optimal (up to log factors) for any algorithm. On the other hand, adversarial corruption, which changes an arbitrary $ζ_0$-fraction of the measurements to any phase-only values, increments $\|\mathbf{x}^\sharp-\mathbf{x}\|_2$ by $O(\sqrt{ζ_0\log(1/ζ_0)})$. The developments are then combined to yield a robust instance optimal guarantee that resembles the standard one in linear compressed sensing.

Junren Chen, Michael K. Ng

A covariance matrix estimator using two bits per entry was recently developed by Dirksen, Maly and Rauhut [Annals of Statistics, 50(6), pp. 3538-3562]. The estimator achieves near minimax rate for general sub-Gaussian distributions, but also suffers from two downsides: theoretically, there is an essential gap on operator norm error between their estimator and sample covariance when the diagonal of the covariance matrix is dominated by only a few entries; practically, its performance heavily relies on the dithering scale, which needs to be tuned according to some unknown parameters. In this work, we propose a new 2-bit covariance matrix estimator that simultaneously addresses both issues. Unlike the sign quantizer associated with uniform dither in Dirksen et al., we adopt a triangular dither prior to a 2-bit quantizer inspired by the multi-bit uniform quantizer. By employing dithering scales varying across entries, our estimator enjoys an improved operator norm error rate that depends on the effective rank of the underlying covariance matrix rather than the ambient dimension, thus closing the theoretical gap. Moreover, our proposed method eliminates the need of any tuning parameter, as the dithering scales are entirely determined by the data. Experimental results under Gaussian samples are provided to showcase the impressive numerical performance of our estimator. Remarkably, by halving the dithering scales, our estimator oftentimes achieves operator norm errors less than twice of the errors of sample covariance.

Junren Chen, Yueqi Wang, Michael K. Ng

Low-rank multivariate regression (LRMR) is an important statistical learning model that combines highly correlated tasks as a multiresponse regression problem with low-rank priori on the coefficient matrix. In this paper, we study quantized LRMR, a practical setting where the responses and/or the covariates are discretized to finite precision. We focus on the estimation of the underlying coefficient matrix. To make consistent estimator that could achieve arbitrarily small error possible, we employ uniform quantization with random dithering, i.e., we add appropriate random noise to the data before quantization. Specifically, uniform dither and triangular dither are used for responses and covariates, respectively. Based on the quantized data, we propose the constrained Lasso and regularized Lasso estimators, and derive the non-asymptotic error bounds. With the aid of dithering, the estimators achieve minimax optimal rate, while quantization only slightly worsens the multiplicative factor in the error rate. Moreover, we extend our results to a low-rank regression model with matrix responses. We corroborate and demonstrate our theoretical results via simulations on synthetic data or image restoration.

Junren Chen, Michael K. Ng

In this paper, we study the estimation performance of empirical $\ell_2$ risk minimization (ERM) in noisy (standard) phase retrieval (NPR) given by $y_k = |α_k^*x_0|^2+η_k$, or noisy generalized phase retrieval (NGPR) formulated as $y_k = x_0^*A_kx_0 + η_k$, where $x_0\in\mathbb{K}^d$ is the desired signal, $n$ is the sample size, $η= (η_1,...,η_n)^\top$ is the noise vector. We establish new error bounds under different noise patterns, and our proofs are valid for both $\mathbb{K}=\mathbb{R}$ and $\mathbb{K}=\mathbb{C}$. In NPR under arbitrary noise vector $η$, we derive a new error bound $O\big(\|η\|_\infty\sqrt{\frac{d}{n}} + \frac{|\mathbf{1}^\topη|}{n}\big)$, which is tighter than the currently known one $O\big(\frac{\|η\|}{\sqrt{n}}\big)$ in many cases. In NGPR, we show $O\big(\|η\|\frac{\sqrt{d}}{n}\big)$ for arbitrary $η$. In both problems, the bounds for arbitrary noise immediately give rise to $\tilde{O}(\sqrt{\frac{d}{n}})$ for sub-Gaussian or sub-exponential random noise, with some conventional but inessential assumptions (e.g., independent or zero-mean condition) removed or weakened. In addition, we make a first attempt to ERM under heavy-tailed random noise assumed to have bounded $l$-th moment. To achieve a trade-off between bias and variance, we truncate the responses and propose a corresponding robust ERM estimator, which is shown to possess the guarantee $\tilde{O}\big(\big[\sqrt{\frac{d}{n}}\big]^{1-1/l}\big)$ in both NPR, NGPR. All the error bounds straightforwardly extend to the more general problems of rank-$r$ matrix recovery, and these results deliver a conclusion that the full-rank frame $\{A_k\}_{k=1}^n$ in NGPR is more robust to biased noise than the rank-1 frame $\{α_kα_k^*\}_{k=1}^n$ in NPR. Extensive experimental results are presented to illustrate our theoretical findings.

Junren Chen, Jonathan Scarlett, Michael K. Ng et al.

In generative compressed sensing (GCS), we want to recover a signal $\mathbf{x}^* \in \mathbb{R}^n$ from $m$ measurements ($m\ll n$) using a generative prior $\mathbf{x}^*\in G(\mathbb{B}_2^k(r))$, where $G$ is typically an $L$-Lipschitz continuous generative model and $\mathbb{B}_2^k(r)$ represents the radius-$r$ $\ell_2$-ball in $\mathbb{R}^k$. Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $\mathbf{x}^*$ rather than for all $\mathbf{x}^*$ simultaneously. In this paper, we build a unified framework to derive uniform recovery guarantees for nonlinear GCS where the observation model is nonlinear and possibly discontinuous or unknown. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. Specifically, using a single realization of the sensing ensemble and generalized Lasso, {\em all} $\mathbf{x}^*\in G(\mathbb{B}_2^k(r))$ can be recovered up to an $\ell_2$-error at most $ε$ using roughly $\tilde{O}({k}/{ε^2})$ samples, with omitted logarithmic factors typically being dominated by $\log L$. Notably, this almost coincides with existing non-uniform guarantees up to logarithmic factors, hence the uniformity costs very little. As part of our technical contributions, we introduce the Lipschitz approximation to handle discontinuous observation models. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy. Experimental results are presented to corroborate our theory.

Junren Chen, Michael K. Ng, Zhaoqiang Liu

The problem of recovering a signal $\boldsymbol x\in \mathbb{R}^n$ from a quadratic system $\{y_i=\boldsymbol x^\top\boldsymbol A_i\boldsymbol x,\ i=1,\ldots,m\}$ with full-rank matrices $\boldsymbol A_i$ frequently arises in applications such as unassigned distance geometry and sub-wavelength imaging. With i.i.d. standard Gaussian matrices $\boldsymbol A_i$, this paper addresses the high-dimensional case where $m\ll n$ by incorporating prior knowledge of $\boldsymbol x$. First, we consider a $k$-sparse $\boldsymbol x$ and introduce the thresholded Wirtinger flow (TWF) algorithm that does not require the sparsity level $k$. TWF comprises two steps: the spectral initialization that identifies a point sufficiently close to $\boldsymbol x$ (up to a sign flip) when $m=O(k^2\log n)$, and the thresholded gradient descent which, when provided a good initialization, produces a sequence linearly converging to $\boldsymbol x$ with $m=O(k\log n)$ measurements. Second, we explore the generative prior, assuming that $x$ lies in the range of an $L$-Lipschitz continuous generative model with $k$-dimensional inputs in an $\ell_2$-ball of radius $r$. With an estimate correlated with the signal, we develop the projected gradient descent (PGD) algorithm that also comprises two steps: the projected power method that provides an initial vector with $O\big(\sqrt{\frac{k \log L}{m}}\big)$ $\ell_2$-error given $m=O(k\log(Lnr))$ measurements, and the projected gradient descent that refines the $\ell_2$-error to $O(δ)$ at a geometric rate when $m=O(k\log\frac{Lrn}{δ^2})$. Experimental results corroborate our theoretical findings and show that: (i) our approach for the sparse case notably outperforms the existing provable algorithm sparse power factorization; (ii) leveraging the generative prior allows for precise image recovery in the MNIST dataset from a small number of quadratic measurements.

Junren Chen, Ming Yuan

This paper provides a unified treatment to the recovery of structured signals living in a star-shaped set from general quantized measurements $\mathcal{Q}(\mathbf{A}\mathbf{x}-\mathbfτ)$, where $\mathbf{A}$ is a sensing matrix, $\mathbfτ$ is a vector of (possibly random) quantization thresholds, and $\mathcal{Q}$ denotes an $L$-level quantizer. The ideal estimator with consistent quantized measurements is optimal in some important instances but typically infeasible to compute. To this end, we study the projected gradient descent (PGD) algorithm with respect to the one-sided $\ell_1$-loss and identify the conditions under which PGD achieves the same error rate, up to logarithmic factors. These conditions include estimates of the separation probability, small-ball probability and some moment bounds that are easy to validate. For multi-bit case, we also develop a complementary approach based on product embedding to show global convergence. When applied to popular models such as 1-bit compressed sensing with Gaussian $\mathbf{A}$ and zero $\mathbfτ$ and the dithered 1-bit/multi-bit models with sub-Gaussian $\mathbf{A}$ and uniform dither $\mathbfτ$, our unified treatment yields error rates that improve on or match the sharpest results in all instances. Particularly, PGD achieves the information-theoretic optimal rate $\tilde{O}(\frac{k}{mL})$ for recovering $k$-sparse signals, and the rate $\tilde{O}((\frac{k}{mL})^{1/3})$ for effectively sparse signals. For 1-bit compressed sensing of sparse signals, our result recovers the optimality of normalized binary iterative hard thresholding (NBIHT) that was proved very recently.

Junren Chen, Yun Yang

Clustering is a fundamental problem in statistics and machine learning. We propose the first one-bit clustering method for two-component sub-Gaussian mixture models. The method uses only one bit per entry of each sample obtained via a dithered quantizer. Under a mild non-spikiness condition on the cluster centers, we show that a variant of Lloyd's algorithm achieves a misclassification rate that decays exponentially with a signal-to-noise ratio comparable to that in the unquantized setting. This result further implies exact recovery under an explicit separation condition, which exceeds the optimal threshold for unquantized data by only a logarithmic factor. When the dimension $p$ is sufficiently large, the non-spikiness condition can be enforced by applying a random rotation using a Haar distributed matrix prior to quantization. In particular, it holds with high probability when $p \gtrsim 1$ for partial recovery and $p \gtrsim \log n \log\log n$ for exact recovery, where $n$ is the sample size. We also establish a minimax lower bound, showing that the misclassification rate and separation condition exhibit sharp constants in general. Numerical results are provided to corroborate the theory and demonstrate the efficacy of the proposed method.

Madison Cotteret, Hugh Greatorex, Alpha Renner et al. · eth-zurich

Programming recurrent spiking neural networks (RSNNs) to robustly perform multi-timescale computation remains a difficult challenge. To address this, we describe a single-shot weight learning scheme to embed robust multi-timescale dynamics into attractor-based RSNNs, by exploiting the properties of high-dimensional distributed representations. We embed finite state machines into the RSNN dynamics by superimposing a symmetric autoassociative weight matrix and asymmetric transition terms, which are each formed by the vector binding of an input and heteroassociative outer-products between states. Our approach is validated through simulations with highly nonideal weights; an experimental closed-loop memristive hardware setup; and on Loihi 2, where it scales seamlessly to large state machines. This work introduces a scalable approach to embed robust symbolic computation through recurrent dynamics into neuromorphic hardware, without requiring parameter fine-tuning or significant platform-specific optimisation. Moreover, it demonstrates that distributed symbolic representations serve as a highly capable representation-invariant language for cognitive algorithms in neuromorphic hardware.

Zhaoqiang Liu, Wen Li, Junren Chen

Generalized eigenvalue problems (GEPs) find applications in various fields of science and engineering. For example, principal component analysis, Fisher's discriminant analysis, and canonical correlation analysis are specific instances of GEPs and are widely used in statistical data processing. In this work, we study GEPs under generative priors, assuming that the underlying leading generalized eigenvector lies within the range of a Lipschitz continuous generative model. Under appropriate conditions, we show that any optimal solution to the corresponding optimization problems attains the optimal statistical rate. Moreover, from a computational perspective, we propose an iterative algorithm called the Projected Rayleigh Flow Method (PRFM) to approximate the optimal solution. We theoretically demonstrate that under suitable assumptions, PRFM converges linearly to an estimated vector that achieves the optimal statistical rate. Numerical results are provided to demonstrate the effectiveness of the proposed method.

Junren Chen, Cheng-Long Wang, Michael K. Ng et al.

In this paper, we propose a uniformly dithered 1-bit quantization scheme for high-dimensional statistical estimation. The scheme contains truncation, dithering, and quantization as typical steps. As canonical examples, the quantization scheme is applied to the estimation problems of sparse covariance matrix estimation, sparse linear regression (i.e., compressed sensing), and matrix completion. We study both sub-Gaussian and heavy-tailed regimes, where the underlying distribution of heavy-tailed data is assumed to have bounded moments of some order. We propose new estimators based on 1-bit quantized data. In sub-Gaussian regime, our estimators achieve near minimax rates, indicating that our quantization scheme costs very little. In heavy-tailed regime, while the rates of our estimators become essentially slower, these results are either the first ones in an 1-bit quantized and heavy-tailed setting, or already improve on existing comparable results from some respect. Under the observations in our setting, the rates are almost tight in compressed sensing and matrix completion. Our 1-bit compressed sensing results feature general sensing vector that is sub-Gaussian or even heavy-tailed. We also first investigate a novel setting where both the covariate and response are quantized. In addition, our approach to 1-bit matrix completion does not rely on likelihood and represent the first method robust to pre-quantization noise with unknown distribution. Experimental results on synthetic data are presented to support our theoretical analysis.

Junren Chen, Michael K. Ng

In this paper, we study color image inpainting as a pure quaternion matrix completion problem. In the literature, the theoretical guarantee for quaternion matrix completion is not well-established. Our main aim is to propose a new minimization problem with an objective combining nuclear norm and a quadratic loss weighted among three channels. To fill the theoretical vacancy, we obtain the error bound in both clean and corrupted regimes, which relies on some new results of quaternion matrices. A general Gaussian noise is considered in robust completion where all observations are corrupted. Motivated by the error bound, we propose to handle unbalanced or correlated noise via a cross-channel weight in the quadratic loss, with the main purpose of rebalancing noise level, or removing noise correlation. Extensive experimental results on synthetic and color image data are presented to confirm and demonstrate our theoretical findings.