کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4950878 1441038 2017 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Relaxed leverage sampling for low-rank matrix completion
ترجمه فارسی عنوان
نمونه گیری اهرم رها شده برای تکمیل ماتریس کم رتبه
کلمات کلیدی
نمره اهرم آرامش بخش، کم رتبه تکمیل ماتریس، هنجار هسته ای، الگوریتم های تصادفی،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We show that any m×n matrix of rank ϱ can be recovered exactly via nuclear norm minimization from Θ(λ⋅log2(m+n)) randomly sampled entries (λ=(m+n)ϱ−ϱ2 being the degrees of freedom), if we observe each entry with probability proportional to the sum of corresponding row and column leverage scores, minus their product. This relaxation in probabilities (as opposed to sum of leverage scores in [1]) can give us O(ϱ2log2(m+n)) additive improvement on the (best known) sample size of [1]. Further, we can use our relaxed leverage score sampling to achieve additive improvement on sample size for exact recovery of (a) incoherent matrices (with restricted leverage scores), and (b) row (or column) incoherent matrices, without knowing the leverage scores a priori.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 124, August 2017, Pages 6-9
نویسندگان
,