論文の概要: One-Sided Matrix Completion from Ultra-Sparse Samples
- arxiv url: http://arxiv.org/abs/2601.12213v1
- Date: Sun, 18 Jan 2026 01:33:48 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-01-21 22:47:22.50779
- Title: One-Sided Matrix Completion from Ultra-Sparse Samples
- Title（参考訳）: 超スパース試料からの1次元マトリックス補完
- Authors: Hongyang R. Zhang, Zhenshuo Zhang, Huy L. Nguyen, Guanghui Lan,
- Abstract要約: 観測周波数で第2モーメントの各非ゼロエントリを正規化する非バイアス推定器を提案する。
推定器は任意の$p$に対して偏りがなく、分散が低いことを示す。
合成データと実世界のデータの両方の実験は、我々のアプローチを検証する。
- 参考スコア（独自算出の注目度）: 18.28432289831719
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Matrix completion is a classical problem that has received recurring interest across a wide range of fields. In this paper, we revisit this problem in an ultra-sparse sampling regime, where each entry of an unknown, $n\times d$ matrix $M$ (with $n \ge d$) is observed independently with probability $p = C / d$, for a fixed integer $C \ge 2$. This setting is motivated by applications involving large, sparse panel datasets, where the number of rows far exceeds the number of columns. When each row contains only $C$ entries -- fewer than the rank of $M$ -- accurate imputation of $M$ is impossible. Instead, we estimate the row span of $M$ or the averaged second-moment matrix $T = M^{\top} M / n$. The empirical second-moment matrix computed from observed entries exhibits non-random and sparse missingness. We propose an unbiased estimator that normalizes each nonzero entry of the second moment by its observed frequency, followed by gradient descent to impute the missing entries of $T$. The normalization divides a weighted sum of $n$ binomial random variables by the total number of ones. We show that the estimator is unbiased for any $p$ and enjoys low variance. When the row vectors of $M$ are drawn uniformly from a rank-$r$ factor model satisfying an incoherence condition, we prove that if $n \ge O({d r^5 ε^{-2} C^{-2} \log d})$, any local minimum of the gradient-descent objective is approximately global and recovers $T$ with error at most $ε^2$. Experiments on both synthetic and real-world data validate our approach. On three MovieLens datasets, our algorithm reduces bias by $88\%$ relative to baseline estimators. We also empirically validate the linear sampling complexity of $n$ relative to $d$ on synthetic data. On an Amazon reviews dataset with sparsity $10^{-7}$, our method reduces the recovery error of $T$ by $59\%$ and $M$ by $38\%$ compared to baseline methods.
- Abstract（参考訳）: 行列完備化は古典的な問題であり、様々な分野において繰り返し関心を集めてきた。
本稿では、未知の$n\times d$ matrix $M$ (with $n \ge d$) の各エントリを、固定整数 $C \ge 2$ に対して確率 $p = C / d$ で独立に観測する超スパースサンプリング方式でこの問題を再検討する。
この設定は、大きなスパースパネルデータセットを含むアプリケーションによって動機付けられており、行の数が列数を超えている。
各行が$C$のエントリ($M$のランクより小さい)しか持たない場合、$M$の正確な計算は不可能である。
代わりに、M$ または平均化された第二モーメント行列 $T = M^{\top} M / n$ の行幅を推定する。
観察された成分から計算された経験的第二モーメント行列は、非ランダムでスパースな欠損を示す。
観測周波数で第2モーメントの各非零エントリを正規化し,その後に勾配降下を行い,欠落した$T$をインプットする非偏差推定器を提案する。
正規化は、合計数で$n$二項確率変数の重み付き和を割る。
推定器は任意の$p$に対して偏りがなく、分散が低いことを示す。
M$ の行ベクトルが非コヒーレンス条件を満たすランク-$r$因子モデルから一様に引かれるとき、$n \ge O({d r^5 ε^{-2} C^{-2} \log d})$ が成り立つと、勾配-退化目的の任意の局所最小値はほぼ大域的であり、最大$ε^2$ の誤差で$T$を回復する。
合成データと実世界のデータの両方の実験は、我々のアプローチを検証する。
3つのMovieLensデータセット上では、ベースライン推定器と比較してバイアスを8,8\%削減する。
また,合成データに対する$d$に対する$n$の線形サンプリング複雑性を実験的に検証した。
Amazonのレビューデータセットを10～7ドルとすることで,ベースラインメソッドと比較して,リカバリエラーが$T$$$59\%,$M$$$$$38\%削減される。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳（メタデータ） (2022-09-30T04:15:44Z) - List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering [42.526664955704746]
そこで我々は,リストデコダブルなスパース平均推定のための,新しい,概念的にシンプルな手法を開発した。
特に、$k$-sparse方向の「確実に有界な」$t-thモーメントを持つ分布の場合、このアルゴリズムは、サンプル複雑性$m = (klog(n))O(t)/alpha(mnt)$の誤差を1/alpha(O (1/t)$で達成する。
Gaussian inliers の特別な場合、我々のアルゴリズムは $Theta (sqrtlog) の最適誤差を保証する。
論文 参考訳（メタデータ） (2022-06-10T17:38:18Z) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文 参考訳（メタデータ） (2021-09-06T14:21:43Z) - Chi-square and normal inference in high-dimensional multi-task
regression [7.310043452300736]
本稿では,Multi-Task(MT)線形モデルにおける未知の係数行列$B*$サイズ$ptimes T$に対するカイ二乗法および正規手法を提案する。
論文 参考訳（メタデータ） (2021-07-16T11:19:49Z) - Likelihood estimation of sparse topic distributions in topic models and
its applications to Wasserstein document distance calculations [3.679981089267181]
トピックモデルでは、$ptimes n$予測ワード頻度行列は$ptimes K$ワードトピック行列$A$として分解される。
A$の列は、すべてのドキュメントに共通する$p$の混合コンポーネントと見なされる。
A$が未知の場合、プラグインに対応する可能性関数を最適化して$T$を見積もる。
論文 参考訳（メタデータ） (2021-07-12T22:22:32Z) - Sparse sketches with small inversion bias [79.77110958547695]
逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。
本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。
スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
論文 参考訳（メタデータ） (2020-11-21T01:33:15Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss [76.02734481158458]
最悪の場合、行列に対する良いランク-$k$近似を得るには、任意に大きい$nOmega(1)$列数が必要であることが知られている。
最小かつ現実的な分布設定では、ほぼ線形な実行時間を持つ$(k/epsilon)$-approximationとpoly$(k/epsilon)+O(klog n)$ columnsが得られる。
これは、エントリワイズで$(k/epsilon)$-approximationを達成するための任意の種類の最初のアルゴリズムである
論文 参考訳（メタデータ） (2020-04-16T22:57:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。