Yaniv Plan
Relevant Thesis-Based Degree Programs
Affiliations to Research Centres, Institutes & Clusters
Graduate Student Supervision
Doctoral Student Supervision
Dissertations completed in 2010 or later are listed below. Please note that there is a 6-12 month delay to add the latest dissertations.
Compressed sensing (CS) is a paradigm in which a structured high-dimensional signal may be recovered from random, under-determined, corrupted linear measurements. LASSO programs are effective for solving CS problems due to their proven ability to leverage underlying signal structure. Three popular LASSO programs are equivalent in a sense and sometimes used interchangeably. Tuned by a governing parameter, each admits an optimal parameter choice yielding minimax order-optimal error. CS is well-studied, though theory for LASSO programs typically concerns this optimally tuned setting. However, the optimal parameter value for a LASSO program depends on properties of the data and is typically unknown in practical settings. Performance in empirical problems thus hinges on a program's parameter sensitivity: it is desirable that small variation about the optimal parameter choice begets small variation about the optimal risk.We examine the risk of three LASSO programs as a function of their governing parameters and further demonstrate that their parameter sensitivity can differ for the same data, thereby informing the selection of a LASSO program in practice. We prove a gauge-constrained program admits asymptotic cusp-like behaviour of its risk in the limiting low-noise regime; a residual-constrained program has asymptotically suboptimal risk for very sparse vectors (i.e., for any fixed parameter choice, the ratio of the risk to the optimally achievable risk grows unbounded). These results contrast observations about an unconstrained program with sufficiently large parameter. Our theory is supported with extensive numerical simulations, demonstrating the parameter sensitivity phenomenon for even modest dimensional parameters.We first analyze these risks for proximal denoising (PD), in which one directly observes signal plus noise (i.e., the measurement matrix is identity). There, we further reveal a data regime in which the unconstrained PD risk can be asymptotically suboptimal. We also show how our theory extends to analyze generalized LASSO programs for generalized CS. Finally, we extend a keystone of our theoretical analysis, the projection lemma. We generalize the result to an arbitrary Hilbert space and extend it from scaled projections to proximal mappings of a dilated gauge. We discuss applications and possible directions for these results.
View record
Tensor completion is the problem of recovering a low-rank tensor from a partial subset of its entries. Assuming a rank-r, order-d tensor in ℝ^{NxNx...N}, the best sampling complexity achieved is O(rN^{d/2}) which can be obtained by a tensor nuclear-norm minimization problem. This bound is significantly larger than O(rdN), the number of free variables in a rank-r tensor. In this thesis, we prove that when r=O(1), we can achieve optimal sample complexity by constraining either one of two proxies for tensor rank, the convex M-norm or the non-convex max-qnorm. The max-qnorm is the generalization of matrix max-norm to tensors which is non-convex. The M-norm, on the other hand, is a convex atomic norm whose atoms are rank-1 sign tensors. We prove that both max-qnorm and M-norm of a bounded rank-r tensor are bounded by quantities that are independent of N. We also prove that the unit balls of both these norms have small Rademacher complexity.We analyze max-qnorm and M-norm constrained least squares minimization problems for tensor completion, proving that when r=O(1), m=O(Nd) measurements are sufficient for efficient estimation of the original tensor. We also use an information theoretic technique to prove that the dependence on N is optimal. Moreover, we design an alternating method for approximating the solution of max-qnorm tensor completion and do a thorough investigation of its performance on synthetic and real-world data.We also generalize the 1-bit matrix completion problem to higher-order tensors. We prove that when r=O(1) a bounded rank-r, order-d tensor T in ℝ^N x ℝ^N x ... x ℝ^N can be estimated efficiently by only m=O(Nd) binary measurements by regularizing either its max-qnorm or its M-norm. We prove that the sample complexity of recovering a low-rank tensor from 1-bit measurements of a subset of its entries is the same as recovering it from unquantized measurements. Moreover, we show the advantage of using 1-bit tensor completion over matricization both theoretically and numerically. Specifically, we show how the 1-bit measurement model can be used for context-aware recommender systems.
View record
Master's Student Supervision
Theses completed in 2010 or later are listed below. Please note that there is a 6-12 month delay to add the latest theses.
In~\cite{bora2017compressed}, a mathematical framework was developed for compressed sensing guarantees in the setting where the measurement matrix is Gaussian and the signal structure is the range of a generative neural network (GNN). The problem of compressed sensing with GNNs has since been extensively analyzed when the measurement matrix and/or network weights follow a subgaussian distribution. In this thesis, we move beyond the subgaussian assumption to measurement matrices that are derived by sampling uniformly at random rows of a unitary matrix (including sub-sampled Fourier measurements as a special case). Specifically, we prove the first known restricted isometry guarantee for generative compressed sensing (GCS) with \emph{sub-sampled isometries}, and provide recovery bounds with nearly order-optimal sample complexity, addressing an open problem of~\cite[p.~10]{scarlett2022theoretical}. Recovery efficacy is characterized by the \emph{coherence}, a new parameter, which measures the interplay between the range of the network and the measurement matrix. Our approach relies on subspace counting arguments and ideas central to high-dimensional probability. Furthermore, we propose a regularization strategy for training GNNs to have favourable coherence with the measurement operator. We provide compelling numerical simulations that support this regularized training strategy: our strategy yields low coherence networks that require fewer measurements for signal recovery. This, together with our theoretical results, supports coherence as a natural quantity for characterizing GCS with sub-sampled isometries.
View record
Spatial transcriptomics goes one step beyond single-cell RNA sequencing, yielding high-dimensional images of gene expression in a tissue, which offer the prospect of understanding cell signaling. Recent breakthroughs in spatial transcriptomics have drastically increased the area of tissue which can be profiled. However, sequencing all RNA molecules over large spatial areas is prohibitively expensive. One would like to reduce the number of RNAs sequenced, but this results in excessive technical noise in the measured gene expression data. To counter this problem, we develop theory and algorithms for spatial transcriptomics denoising, based on low rank matrix recovery and spatial smoothing. We propose two novel procedures for estimating the true underlying gene expression image: (1) a low rank maximum-likelihood-type estimator with graph-based total variation regularization, and (2) a switching procedure that switches between 'risky' estimators that work well in practice, and 'safe' estimators which have well-known properties. Our methods are backed by theoretical recovery guarantees, as well as tests on real data which suggest that it is possible to reduce the number of RNAs sequenced by more than 10-fold, without significantly increasing recovery error. Finally, as a generalization of the analysis employed above, we establish some convergence rates for the estimation of structured discrete probability distributions.
View record
We study the problem of reconstructing a high-dimensional signal x∈ℝⁿ from a low-dimensional noisy linear measurement y=Mx+e∈ℝˡ, assuming x admits a certain structure. We model the measurement matrix as M=BA, with arbitrary B∈ℝˡˣᵐ and sub-gaussian A∈ℝᵐˣⁿ; therefore allowing for a family of random measurement matrices which may have heavy tails, dependent rows and columns, and a large dynamic range for the singular values. The structure is either given as a non-convex cone T⊂ℝⁿ, or is induced via minimizing a given convex function f(·). We prove, in both cases, that an approximate empirical risk minimizer robustly recovers the signal if the effective number of measurements is sufficient, even in the presence of a model mismatch. While in classical compressed sensing the number of independent (sub)-gaussian measurements regulates the possibility of a robust reconstruction, here in our setting the effective number of measurements depends on the properties of B. We show that, in this model, the stable rank of B indicates the effective number of measurements, and an accurate recovery is guaranteed whenever it exceeds the effective dimension of the structure set. We apply our results to the special case of generative priors, i.e. when x is close to the range of a Generative Neural Network (GNN) with ReLU activation functions. Also, if the GNN has random weights in the last layer, our theory allows a partial Fourier measurement matrix, thus taking the first step in a theoretical analysis of compressed sensing MRI with GNN. Our work relies on a recent result in random matrix theory by Jeong, Li, Plan, and Yilmaz.
View record
If this is your researcher profile you can log in to the Faculty & Staff portal to update your details and provide recruitment preferences.