Ozgur Yilmaz

Professor

Relevant Degree Programs

 

Graduate Student Supervision

Doctoral Student Supervision (Jan 2008 - May 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

Master's Student Supervision (2010 - 2018)
A weighted ℓ₁-minimization for distributed compressive sensing (2015)

Distributed Compressive Sensing (DCS) studies the recovery of jointly sparse signals. Compared to separate recovery, the joint recovery algorithms in DCS are usually more effective as they make use of the joint sparsity. In this thesis, we study a weighted ℓ₁-minimization algorithm for the joint sparsity model JSM-1 proposed by Baron et al. Our analysis gives a sufficient null space property for the joint sparse recovery. Furthermore, this property can be extended to stable and robust settings. We also presents some numerical experiments for this algorithm.

View record

Sparse signal recovery : analysis and synthesis formulations with prior support information (2014)

The synthesis model for signal recovery has been the model of choice for many years in compressive sensing. Various weighting schemes using prior support information to adjust the objective function associated with the synthesis model have been shown to improve the recovery of the signal in terms of accuracy. Generally, even with no prior knowledge of the support, iterative methods can build support estimates and incorporate that into therecovery which has also been shown to increase the speed and accuracy of the recovery. However when the original signal is sparse with respect to a redundant dictionary (rather than an orthonormal basis) there is a coun-terpart model to synthesis, namely the analysis model, which has been less popular but has recently attracted more attention. The analysis model is much less understood and thus there are fewer theorems available in both the context of non-weighted and weighted signal recovery.In this thesis, we investigate weighting in both the analysis model and synthesis model in weighted l-1 minimization. Theoretical guarantees on reconstruction and various weighting strategies for each model are discussed. We give conditions for weighted synthesis recovery with frames which do not require strict incoherency conditions, this is based on recent results of regular synthesis with frames using optimal dual l-1 analysis. A novel weighting technique is introduced in the analysis case which outperforms its traditional counterparts in the case of seismic wavefield reconstruction. We also introduce a weighted split Bregman algorithm for analysis and optimaldual analysis. We then investigate these techniques on seismic data and synthetically created test data using a variety of frames.

View record

 

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.