論文の概要: Provably Finding a Hidden Dense Submatrix among Many Planted Dense Submatrices via Convex Programming

• arxiv url: http://arxiv.org/abs/2601.03946v1
• Date: Wed, 07 Jan 2026 14:02:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-09 02:15:23.578526
• Title: Provably Finding a Hidden Dense Submatrix among Many Planted Dense Submatrices via Convex Programming
• Title（参考訳）: 凸プログラミングによる多くの緑化デンスサブマトリクス中の隠れデンスサブマトリクスの発見の可能性
• Authors: Valentine Olanubi, Phineas Agar, Brendan Ames,
• Abstract要約: 我々は、最も非ゼロなエントリを含む与えられた二項行列の固定サイズの部分行列を求める最も密度の高い部分行列問題を考える。 近年の研究では、最も密度の高い部分行列問題の正確な解法のための十分な条件の開発に焦点が当てられている。 これらの結果は、入力行列がエンファニーの大きい高密度部分グラフを含むようなより現実的な設定にまで拡張する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the densest submatrix problem, which seeks the submatrix of fixed size of a given binary matrix that contains the most nonzero entries. This problem is a natural generalization of fundamental problems in combinatorial optimization, e.g., the densest subgraph, maximum clique, and maximum edge biclique problems, and has wide application the study of complex networks. Much recent research has focused on the development of sufficient conditions for exact solution of the densest submatrix problem via convex relaxation. The vast majority of these sufficient conditions establish identification of the densest submatrix within a graph containing exactly one large dense submatrix hidden by noise. The assumptions of these underlying models are not observed in real-world networks, where the data may correspond to a matrix containing many dense submatrices of varying sizes. We extend and generalize these results to the more realistic setting where the input matrix may contain \emph{many} large dense subgraphs. Specifically, we establish sufficient conditions under which we can expect to solve the densest submatrix problem in polynomial time for random input matrices sampled from a generalization of the stochastic block model. Moreover, we also provide sufficient conditions for perfect recovery under a deterministic adversarial. Numerical experiments involving randomly generated problem instances and real-world collaboration and communication networks are used empirically to verify the theoretical phase-transitions to perfect recovery given by these sufficient conditions.
• Abstract（参考訳）: 我々は、最も非ゼロなエントリを含む与えられた二項行列の固定サイズの部分行列を求める最も密度の高い部分行列問題を考える。 この問題は、組合せ最適化の基本問題、例えば、最も密度の高い部分グラフ、最大斜め、最大辺双斜め問題の自然な一般化であり、複雑なネットワークの研究に広く応用されている。 近年の研究では、凸緩和による最も密度の高い部分行列問題の正確な解法のための十分な条件の開発に焦点が当てられている。 これらの十分条件の大部分は、ノイズによって隠されたちょうど1つの大きな密度のサブマトリクスを含むグラフの中で最も密度の高いサブマトリクスの同定を確立する。 これらの基礎となるモデルの仮定は実世界のネットワークでは観測されず、そこではデータは様々な大きさの多くの密度のサブマトリクスを含む行列に対応する。 我々はこれらの結果を、入力行列が \emph{many} の大きな高密度部分グラフを含むようなより現実的な設定に拡張して一般化する。 具体的には,確率ブロックモデルの一般化からサンプリングしたランダムな入力行列に対して,多項式時間で最も高密度な部分行列問題を解くことを期待できる十分な条件を確立する。 また,決定論的逆境下での完全回復に十分な条件も提供する。 ランダムに生成された問題インスタンスと実世界の協調・通信ネットワークを含む数値実験は、これらの十分な条件によって与えられる理論的な位相遷移を検証するために経験的に使用される。

関連論文リスト

• The Structural Complexity of Matrix-Vector Multiplication [0.10485739694839669]
  行列ベクトル乗算問題は$tildeO(n2)$プレプロセッシングと$tildeO(n2-1/d)$クエリ時間で解けることを示す。 我々の結果は、多くの応用において最初の非自明な上界が得られる。
  論文  参考訳（メタデータ） (2025-02-28T17:11:36Z)
• Entry-Specific Bounds for Low-Rank Matrix Completion under Highly Non-Uniform Sampling [10.824999179337558]
  行列全体よりも小さい部分行列上で推定アルゴリズムを実行する方がよく、時には最適であることを示す。 我々の境界は、各エントリを局所的なサンプリング確率の関数として推定する難しさを特徴付ける。
  論文  参考訳（メタデータ） (2024-02-29T23:24:43Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  本稿では,初期監視情報を同時に拡張し,識別親和性行列を構築することのできる,新しい半教師付きサブスペースクラスタリング手法を提案する。 6つの一般的なベンチマークデータセットの総合的な実験結果から,本手法が最先端手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-05-21T01:47:17Z)
• Learning a Compressive Sensing Matrix with Structural Constraints via Maximum Mean Discrepancy Optimization [17.104994036477308]
  本稿では,圧縮センシング関連回復問題に対する測定行列を得るための学習に基づくアルゴリズムを提案する。 ニューラルネットワーク関連のトピックにおけるこのようなメトリクスの最近の成功は、機械学習に基づく問題の解決策を動機付けている。
  論文  参考訳（メタデータ） (2021-10-14T08:35:54Z)
• Identifiability in Exact Two-Layer Sparse Matrix Factorization [0.0]
  スパース行列分解(sparse matrix factorization)は、L スパース因子 X(L) X(L--1) の積による行列 Z の近似の問題である。 本稿では,この問題に現れる識別可能性の問題に焦点をあてる。
  論文  参考訳（メタデータ） (2021-10-04T07:56:37Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。 そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-30T19:17:35Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  非PSDおよび2乗根行列の次元削減法を提案する。 複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2021-06-16T04:07:48Z)
• Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
  我々は弱い教師付き回帰問題を解く。 weakly"の下では、いくつかのトレーニングポイントではラベルが知られ、未知のものもあれば、無作為なノイズの存在やリソースの欠如などの理由によって不確かであることが分かっています。 数値的な節ではモンテカルロモデルを用いて提案手法を人工と実のデータセットに適用した。
  論文  参考訳（メタデータ） (2021-04-13T23:21:01Z)
• Eigendecomposition-Free Training of Deep Networks for Linear Least-Square Problems [107.3868459697569]
  我々は、ディープネットワークのトレーニングに固有分解のないアプローチを導入する。 この手法は固有分解の明示的な微分よりもはるかに堅牢であることを示す。 我々の手法は収束特性が良く、最先端の結果が得られます。
  論文  参考訳（メタデータ） (2020-04-15T04:29:34Z)
• Relative Error Bound Analysis for Nuclear Norm Regularized Matrix Completion [101.83262280224729]
  我々は、原子核ノルム正規化行列補完に対する相対誤差を開発する。 未知行列の最適低ランク近似を回復するための相対上界を導出する。
  論文  参考訳（メタデータ） (2015-04-26T13:12:16Z)

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

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