論文の概要: Efficient Algorithms for Verifying Kruskal Rank in Sparse Linear Regression and Related Applications

• arxiv url: http://arxiv.org/abs/2503.04986v1
• Date: Thu, 06 Mar 2025 21:32:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-10 12:20:28.524683
• Title: Efficient Algorithms for Verifying Kruskal Rank in Sparse Linear Regression and Related Applications
• Title（参考訳）: Sparse Linear RegressionにおけるKruskal Rankの効率的な検証アルゴリズムとその応用
• Authors: Fengqin Zhou,
• Abstract要約: 我々のフレームワークはランダム化ハッシュ技術と動的プログラミング戦略を組み合わせている。 我々のアルゴリズムは、高い確率的正確性を確保しつつ、$mathcalOleft(dk cdot left(nMright)lceil k / 2 rceilright)$のランタイムを実現する。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: We present novel algorithmic techniques to efficiently verify the Kruskal rank of matrices that arise in sparse linear regression, tensor decomposition, and latent variable models. Our unified framework combines randomized hashing techniques with dynamic programming strategies, and is applicable in various settings, including binary fields, general finite fields, and integer matrices. In particular, our algorithms achieve a runtime of $\mathcal{O}\left(dk \cdot \left(nM\right)^{\lceil k / 2 \rceil}\right)$ while ensuring high-probability correctness. Our contributions include: A unified framework for verifying Kruskal rank across different algebraic settings; Rigorous runtime and high-probability guarantees that nearly match known lower bounds; Practical implications for identifiability in tensor decompositions and deep learning, particularly for the estimation of noise transition matrices.
• Abstract（参考訳）: 本稿では, 疎線形回帰, テンソル分解, 潜在変数モデルにおいて生じる行列のクルスカルランクを効率的に検証するアルゴリズムを提案する。 我々の統合されたフレームワークはランダム化ハッシュ手法と動的プログラミング戦略を組み合わせており、二進体、一般有限体、整数行列など様々な設定に適用できる。 特に、我々のアルゴリズムは高確率の正しさを確保しつつ、$\mathcal{O}\left(dk \cdot \left(nM\right)^{\lceil k / 2 \rceil}\right)$のランタイムを達成する。 我々の貢献は以下のとおりである: 異なる代数的設定におけるクルスカル階数検証のための統一的なフレームワーク; 厳密なランタイムと高確率保証は既知の下界にほぼ一致する; テンソル分解およびディープラーニングにおける識別可能性、特にノイズ遷移行列の推定のための実践的意味。

関連論文リスト

• A general error analysis for randomized low-rank approximation with application to data assimilation [42.57210316104905]
  中心行列および非標準行列に対するフロベニウスノルムにおける低ランク近似誤差の解析のための枠組みを提案する。 最小限の仮定の下では、期待と確率の正確な境界を導出する。 私たちの境界には、プロパティを導出し、実践的な選択を動機付けるための明確な解釈があります。
  論文  参考訳（メタデータ） (2024-05-08T04:51:56Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Learning the Positions in CountSketch [49.57951567374372]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-11T07:28:35Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  共分散行列の明示的な構成を避ける新しい推論手法を提案する。 本手法では, 数値線形代数と共役勾配アルゴリズムの対角線推定結果とを結合する。 いくつかのシミュレーションにおいて,本手法は計算時間とメモリにおける既存手法よりも拡張性が高い。
  論文  参考訳（メタデータ） (2022-02-25T16:35:26Z)
• Splitting numerical integration for matrix completion [0.0]
  低階行列近似のための新しいアルゴリズムを提案する。 このアルゴリズムは最適化の枠組みにおける古典的な勾配勾配の適応である。 実験結果から,本手法は大規模問題に対して優れたスケーラビリティを有することが示された。
  論文  参考訳（メタデータ） (2022-02-14T04:45:20Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。 そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-30T19:17:35Z)
• Fast Low-Rank Tensor Decomposition by Ridge Leverage Score Sampling [5.740578698172382]
  リッジレバレッジスコア (ridge leverage scores) と呼ばれるランダム化数値線形代数のタッカー分解とツールの利用について検討する。 近似リッジレバレッジスコアを用いて、任意のリッジ回帰問題に対してスケッチされたインスタンスを構築する方法を示す。 本研究では, 合成データと実世界のデータの両方に対して, 大規模かつ低ランクのタッカー分解に対する近似リッジ回帰アルゴリズムの有効性を示す。
  論文  参考訳（メタデータ） (2021-07-22T13:32:47Z)
• Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
  我々は弱い教師付き回帰問題を解く。 weakly"の下では、いくつかのトレーニングポイントではラベルが知られ、未知のものもあれば、無作為なノイズの存在やリソースの欠如などの理由によって不確かであることが分かっています。 数値的な節ではモンテカルロモデルを用いて提案手法を人工と実のデータセットに適用した。
  論文  参考訳（メタデータ） (2021-04-13T23:21:01Z)
• Provably Convergent Working Set Algorithm for Non-Convex Regularized Regression [0.0]
  本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。 その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
  論文  参考訳（メタデータ） (2020-06-24T07:40:31Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  最小二乗問題に対する反復スケッチの性能について検討する。 本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。 これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
  論文  参考訳（メタデータ） (2020-02-03T16:17:50Z)

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

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