ترجمه فارسی مقاله نمونه‌برداری ساده و تقریباً بهینه برای تکمیل تانسور رتبه ۱ از طریق گاوس-جردن

چکیده

We revisit the sample and computational complexity of completing a rank-1 tensor in $otimes_{i=1}^{N} mathbb{R}^{d}$, given a uniformly sampled subset of its entries. We present a characterization of the problem (i.e. nonzero entries) which admits an algorithm amounting to Gauss-Jordan on a pair of random linear systems. For example, when $N = Θ(1)$, we prove it uses no more than $m = O(d^2 log d)$ samples and runs in $O(md^2)$ time. Moreover, we show any algorithm requires $Ω(dlog d)$ samples. By contrast, existing upper bounds on the sample complexity are at least as large as $d^{1.5} μ^{Ω(1)} log^{Ω(1)} d$, where $μ$ can be $Θ(d)$ in the worst case. Prior work obtained these looser guarantees in higher rank versions of our problem, and tend to involve more complicated algorithms.

چکیده به فارسی (ترجمه ماشینی)

ما نمونه و پیچیدگی محاسباتی تکمیل یک تانسور رتبه 1 را در $ otimes_ {i = 1}^{n} mathbb {r}^{d} $ ، با توجه به یک زیر مجموعه نمونه ای از ورودی های خود ، دوباره بررسی می کنیم.ما یک خصوصیات مسئله (یعنی ورودی های Nonzero) را ارائه می دهیم که الگوریتمی را که به گاوس-یوردان بر روی یک جفت سیستم خطی تصادفی می پذیرد ، می پذیرد.به عنوان مثال ، هنگامی که $ n = θ (1) $ ، ما ثابت می کنیم که بیش از $ m = o (d^2 log d) نمونه ها استفاده نمی کند و در زمان $ o (md^2) $ اجرا می شود.علاوه بر این ، ما نشان می دهیم که هر الگوریتم به نمونه $ $ (d log d) $ نیاز دارد.در مقابل ، مرزهای فوقانی موجود در پیچیدگی نمونه حداقل به اندازه $ d^{1.5} μ^{ω (1)} log^{ω (1)} d $ ، جایی که $ μ $ می تواند $ θ باشد.(د) $ در بدترین حالت.کار قبلی این ضمانت های شل کننده را در نسخه های بالاتر از مشکل ما به دست آورد و تمایل به الگوریتم های پیچیده تر داشت.