Yaniv Plan

Assistant Professor

Relevant Degree Programs

Affiliations to Research Centres, Institutes & Clusters

 
 

Graduate Student Supervision

Doctoral Student Supervision (Jan 2008 - Nov 2019)
Near-optimal sample complexity for noisy or 1-bit tensor completion (2018)

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

Prospective Student Info Sessions

Faculty of Science Information Session

Date: Tuesday, 24 November 2020
Time: 10:00 to 11:00
UBC’s Faculty of Science is home to an array of outstanding scientists and students who strive to unravel the principles that underlie our universe - from the subatomic to the macroscopic, from pure mathematics to biotechnology, from ecosystems to galactic systems. In this session hosted by Professor Mark MacLachlan, Associate Dean of Research & Graduate Studies, we’ll hear from faculty members and graduate students on some of the exciting research happening within the Faculty of Science. We’ll also take a look at the wide range of graduate programs available, what its like to be a grad student in Science, and also provide some application advice. Be sure to join us and get an insight into how UBC Science is discovering new scientific knowledge and preparing Canada’s and the world’s next generation of scientists.
 

Membership Status

Member of G+PS
View explanation of statuses

Program Affiliations

 

If this is your researcher profile you can log in to the Faculty & Staff portal to update your details and provide recruitment preferences.

 
 

Learn about our faculties, research, and more than 300 programs in our 2021 Graduate Viewbook!