論文の概要: Matrix Reordering for Noisy Disordered Matrices: Optimality and Computationally Efficient Algorithms

• arxiv url: http://arxiv.org/abs/2201.06438v2
• Date: Sun, 13 Aug 2023 13:54:10 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-15 23:47:19.211851
• Title: Matrix Reordering for Noisy Disordered Matrices: Optimality and Computationally Efficient Algorithms
• Title（参考訳）: 雑音障害行列に対する行列順序付け:最適性と計算効率の良いアルゴリズム
• Authors: T. Tony Cai and Rong Ma
• Abstract要約: 単細胞生物学とメダゲノミクスの応用により,ノイズモノトンToeplitz行列モデルに基づく行列化の問題を考察した。 我々は、決定理論の枠組みでこの問題の基本的な統計的限界を確立し、制約付き最小二乗率を示す。 そこで本研究では,性能向上を保証した新しい時間適応ソートアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 9.245687221460654
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Motivated by applications in single-cell biology and metagenomics, we investigate the problem of matrix reordering based on a noisy disordered monotone Toeplitz matrix model. We establish the fundamental statistical limit for this problem in a decision-theoretic framework and demonstrate that a constrained least squares estimator achieves the optimal rate. However, due to its computational complexity, we analyze a popular polynomial-time algorithm, spectral seriation, and show that it is suboptimal. To address this, we propose a novel polynomial-time adaptive sorting algorithm with guaranteed performance improvement. Simulations and analyses of two real single-cell RNA sequencing datasets demonstrate the superiority of our algorithm over existing methods.
• Abstract（参考訳）: 単細胞生物学とメダゲノミクスの応用により,雑音に乱れた単調なToeplitz行列モデルに基づく行列再構成の問題点を考察した。 決定論的枠組みにおいて,この問題に対する基本的な統計的限界を定め,制約付き最小二乗推定器が最適速度を達成することを示す。 しかし,計算の複雑さから,一般的な多項式時間アルゴリズムであるスペクトルセレーションを解析し,サブオプティマイズであることを示す。 そこで本研究では,性能向上を保証した多項式時間適応ソートアルゴリズムを提案する。 2つの実シングルセルRNAシークエンシングデータセットのシミュレーションと解析は、既存の手法よりもアルゴリズムの方が優れていることを示す。

関連論文リスト

• Optimality of Approximate Message Passing Algorithms for Spiked Matrix Models with Rotationally Invariant Noise [12.64438771302935]
  本研究では,信号に加法的回転不変雑音を付加して発生する観測行列からランク1信号行列を推定する問題について検討する。 この問題に対する近似メッセージパッシングアルゴリズムの新たなクラスを開発し、高次元極限におけるそれらのダイナミクスの簡易かつ簡潔な特徴付けを提供する。
  論文  参考訳（メタデータ） (2024-05-28T11:42:51Z)
• Dynamic Incremental Optimization for Best Subset Selection [15.8362578568708]
  最良のサブセット選択は、多くの学習問題に対する金の標準と見なされている。 主問題構造と双対問題構造に基づいて,効率的な部分集合双対アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-02-04T02:26:40Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• A fast Multiplicative Updates algorithm for Non-negative Matrix Factorization [2.646309221150203]
  本稿では,各サブプロブレムに対してヘッセン行列のより厳密な上界を構築することにより,乗法更新アルゴリズムの改善を提案する。 コンバージェンスはまだ保証されており、我々は実際に合成と実世界の両方のデータセットで、提案したfastMUアルゴリズムが通常の乗算更新アルゴリズムよりも数桁高速であることを示す。
  論文  参考訳（メタデータ） (2023-03-31T12:09:36Z)
• Adaptive Stochastic Optimisation of Nonconvex Composite Objectives [2.1700203922407493]
  一般化された複合ミラー降下アルゴリズムの一群を提案し,解析する。 適応的なステップサイズでは、提案アルゴリズムは問題の事前知識を必要とせずに収束する。 決定集合の低次元構造を高次元問題に活用する。
  論文  参考訳（メタデータ） (2022-11-21T18:31:43Z)
• Fast Projected Newton-like Method for Precision Matrix Estimation under Total Positivity [15.023842222803058]
  現在のアルゴリズムはブロック座標降下法や近点アルゴリズムを用いて設計されている。 本稿では,2次元投影法に基づく新しいアルゴリズムを提案し,慎重に設計された探索方向と変数分割方式を取り入れた。 合成および実世界のデータセットに対する実験結果から,提案アルゴリズムは最先端の手法と比較して計算効率を著しく向上させることを示した。
  論文  参考訳（メタデータ） (2021-12-03T14:39:10Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。 提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
  論文  参考訳（メタデータ） (2020-12-29T04:08:38Z)
• Multi-View Spectral Clustering with High-Order Optimal Neighborhood Laplacian Matrix [57.11971786407279]
  マルチビュースペクトルクラスタリングは、データ間の固有のクラスタ構造を効果的に明らかにすることができる。 本稿では,高次最適近傍ラプラシア行列を学習するマルチビュースペクトルクラスタリングアルゴリズムを提案する。 提案アルゴリズムは, 1次ベースと高次ベースの両方の線形結合の近傍を探索し, 最適ラプラシア行列を生成する。
  論文  参考訳（メタデータ） (2020-08-31T12:28:40Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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