論文の概要: Sharp Restricted Isometry Thresholds for Global Minima of Rank-Restricted Matrix LASSO

• arxiv url: http://arxiv.org/abs/2608.29018v1
• Date: Sat, 29 Aug 2026 03:13:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-01 18:31:30.817487
• Title: Sharp Restricted Isometry Thresholds for Global Minima of Rank-Restricted Matrix LASSO
• Title（参考訳）: ランク制限行列LASSOの大域最小値に対するシャープ制限等尺閾値
• Abstract要約: ターゲットランク $r_star$ に対して、ランク-$k$ RIP 定数が $_mathrmsharp(k/r_star)$ を満たすなら、結果は通常の凸行列 LASSO に特化する。 我々は,大域最小化器が真理を回復できない反例が存在するため,閾値$_mathrmsharp(k/r_star)$は改善できないことを示す。
• 参考スコア（独自算出の注目度）: 7.969977930633441
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We determine the sharp restricted isometry threshold for recovery at global minima of the rank-restricted matrix LASSO. For target rank $r_{\star}$, if the rank-$k$ RIP constant satisfies $δ<δ_{\mathrm{sharp}}(k/r_{\star})$, where $δ_{\mathrm{sharp}}(t)=t/(4-t)$ for $0<t<4/3$ and $δ_{\mathrm{sharp}}(t)=\sqrt{(t-1)/t}$ for $t\ge4/3$, then every global minimizer has Frobenius error $\lesssim\sqrt{r_{\star}}λ$ for all $λ\gtrsim\|\mathcal{A}^{*}(ξ)\|_{\mathrm{op}}$ and at every search rank $r\ge r_{\star}$. The constants depend only on the RIP constant and $t=k/r_{\star}$, and in particular are independent of the search rank. When the rank restriction is inactive, the result specializes to the ordinary convex matrix LASSO. We also obtain the analogous results for sparsity-restricted vector LASSO. Conversely, we show that the threshold $δ<δ_{\mathrm{sharp}}(k/r_{\star})$ cannot be improved, due to the existence of counterexamples whose global minimizers fail to recover the ground truth.
• Abstract（参考訳）: 我々は、ランク制限行列LASSOの大域最小値での回復のための鋭い制限等尺しきい値を決定する。 ターゲットランク $r_{\star}$ に対して、ランク-$k$ RIP 定数が $δ<δ_{\mathrm{sharp}}(k/r_{\star})$, where $δ_{\mathrm{sharp}}(t)=t/(4-t)$ for $0<t<4/3$ and $δ_{\mathrm{sharp}}(t)=\sqrt{(t-1)/t}$ for $t\ge4/3$ を満足するなら、すべての大域最小化器はフロベニウス誤差 $\lesssim\sqrt{r_{\star}}λ$$ for all $λ\gtrsim\|\mathcal{A}^{*}()||_{\mathrm{op}}$$$$ $0<t<4/3$ and $δ_{\mathrm{sharp}}(t)=\sqrt{(t-1)/t}$ for $t\ge4/3$ である。 定数は RIP 定数と $t=k/r_{\star}$ にのみ依存し、特に探索ランクとは独立である。 ランク制限が不活発な場合、結果は通常の凸行列LASSOに特化する。 また,空間制限ベクトルLASSOの類似結果を得た。 逆に、大域最小化器が基底真理を回復できない反例が存在するため、閾値$δ<δ_{\mathrm{sharp}}(k/r_{\star})$は改善できない。

関連論文リスト

• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  AxiotisとSviridenkoは[AS21]において、凸最適化における制限条件数への線形依存はスパース時間アルゴリズムでは改善できないと推測した。 我々は、最小二乗目的に対する予想下界を確立し、ランダム化された完全体積小セット展開仮説に基づく条件付けを行う。
  論文  参考訳（メタデータ） (2026-08-03T17:57:01Z)
• What Can Be Recovered Under Sparse Adversarial Corruption? Assumption-Free Theory for Linear Measurements [42.543830499945926]
  我々は$xstar$を含む最小の集合を求め、$e$を知らずに$y$から一様に回収できる。 主な結果は、$xstar + ker(U)$で、$U$は2q$行を削除して得られる$A$の可能なすべてのサブ行列の行空間の交点上の一意のプロジェクション行列であることを示している。
  論文  参考訳（メタデータ） (2025-10-28T09:29:46Z)
• Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
  我々は、最近提案された$ell$-smoothness条件$|nabla2f(x)|| le ellleft(||nabla f(x)||right),$$$L$-smoothnessと$(L_0,L_1)$-smoothnessを一般化する関数を持つ凸最適化問題の一階法について検討する。
  論文  参考訳（メタデータ） (2025-08-09T08:28:06Z)
• Low-rank Matrix Bandits with Heavy-tailed Rewards [55.03293214439741]
  アンダーライン重み付きアンダーラインリワード(LowHTR)を用いたアンダーラインローランク行列バンディットの問題点について検討する。 観測されたペイオフに対するトランケーションと動的探索を利用して,LOTUSと呼ばれる新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-04-26T21:54:31Z)
• Convergence of Gradient Descent with Small Initialization for Unregularized Matrix Completion [21.846732043706318]
  バニラ勾配降下は、明示的な正則化を必要とせず、必ず基底真理$rmXstar$に収束することを示す。 驚くべきことに、収束率も最終的な精度もオーバーパラメータ化された検索ランク$r'$に依存しておらず、それらは真のランク$r$によってのみ支配される。
  論文  参考訳（メタデータ） (2024-02-09T19:39:23Z)
• A General Algorithm for Solving Rank-one Matrix Sensing [15.543065204102714]
  マトリックスセンシングの目標は、一連の測定に基づいて、mathbbRn×n$の行列$A_starを復元することである。 本稿では、このランク-$kの仮定を緩和し、より一般的な行列センシング問題を解く。
  論文  参考訳（メタデータ） (2023-03-22T04:07:26Z)
• Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization [10.787390511207683]
  二つの微分可能な$L$-smooth, $mu$-strongly convex objective $phimph over a $ntimes n$frac14(L/mu-1)2rstar$を考える。 非局所性にもかかわらず、局所最適化は、任意の初期点から大域的最適点へグローバルに収束することが保証される。
  論文  参考訳（メタデータ） (2022-07-05T03:18:17Z)
• Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certification [19.32160757444549]
  非函数 $f(X)=phi(XXT)$ を$ntimes r$ factor matrix $X$ で最小化するために勾配降下を考える。 本稿では,勾配降下の収束率を線形に戻すための安価なプレコンディショナーを提案する。
  論文  参考訳（メタデータ） (2022-06-07T14:26:49Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。 実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
  論文  参考訳（メタデータ） (2021-05-17T16:40:48Z)
• Sharp Global Guarantees for Nonconvex Low-rank Recovery in the Noisy Overparameterized Regime [10.787390511207683]
  本稿では,従来の競合する2つのアプローチを統一し,単純化し,強化する新しい証明手法を提案する。 近2次点が,より高価な凸法と同じミニマックス回復限界を達成することを示す。
  論文  参考訳（メタデータ） (2021-04-21T23:07:18Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• The Average-Case Time Complexity of Certifying the Restricted Isometry Property [66.65353643599899]
  圧縮センシングにおいて、100万倍のN$センシング行列上の制限等尺性(RIP)はスパースベクトルの効率的な再構成を保証する。 Mtimes N$ matrices with i.d.$mathcalN(0,1/M)$ entry。
  論文  参考訳（メタデータ） (2020-05-22T16:55:01Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。