論文の概要: Pattern-Based Matrix Analysis Under Permutations
- arxiv url: http://arxiv.org/abs/2611.17674v1
- Date: Fri, 13 Nov 2026 02:39:06 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-16 18:43:16.293525
- Title: Pattern-Based Matrix Analysis Under Permutations
- Title(参考訳): 変動を考慮したパターンベース行列解析
- Abstract要約: 低ランク近似は、行列の単純さという重要な概念をつかむ: 行列は、低次元線型モデルによってうまく記述されている場合、単純である。
列や列を置換した後のみ構造的に単純になる行列を考えると、その質量は所定の幾何学的パターンに集中する。
最適再注文後の行列が与えられたパターンにどの程度近いかを測定するパターン距離を導入する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Low-rank approximation captures one important notion of matrix simplicity: a matrix is simple if it is well described by a low-dimensional linear model. This paper studies a complementary notion. We consider matrices that become structurally simple only after permuting rows and columns, so that their mass concentrates in a prescribed geometric pattern such as a band, block-diagonal, arrowhead, or related form. We introduce a pattern distance that measures how close a matrix is to a given pattern after optimal reordering, giving a common framework for structural problems such as latent ordering, community detection, and bandwidth minimization. The problem is NP-hard in general; we derive an alternating algorithm based on Linear Assignment subproblems. We further introduce a pattern-plus-low-rank decomposition that combines permutation-structured fitting with a low-rank residual, whose permutation step is pattern fitting on the residual; its gains across pattern families persist at a matched parameter budget and are substantially reduced under a density-matched random-mask control. We evaluate the framework on synthetic recovery tasks, real correlation and graph adjacency matrices, and transformer attention heads, showing that a single universal algorithm recovers qualitatively different forms of matrix structure.
- Abstract(参考訳): 低ランク近似は、行列の単純さという重要な概念をつかむ: 行列は、低次元線型モデルによってうまく記述されている場合、単純である。
本稿では相補的な概念について考察する。
列や列を置換した後のみ構造的に単純になる行列を考えると、その質量は、バンド、ブロック対角、矢印、または関連する形式などの所定の幾何学的パターンに集中する。
本稿では,行列が最適再注文後のパターンにどの程度近いかを測定するパターン距離を導入し,遅延順序付けやコミュニティ検出,帯域幅最小化といった構造問題に対する共通の枠組みを提供する。
問題は一般にNPハードであり、線形アサインメントサブプロブレムに基づく交互アルゴリズムを導出する。
さらに, パターンファミリ間の利得が一致したパラメータ予算で持続し, 密度マッチングされたランダムマスク制御の下で大幅に減少するパターンファミリを, 低ランク残差の置換構造と組み合わせたパターンプラス低ランク分解を導入する。
本研究では, 合成回復タスク, 実相関, グラフ隣接行列, トランスフォーマーアテンションヘッドの枠組みを評価し, 1つの普遍的アルゴリズムが定性的に異なる行列構造を復元することを示す。
関連論文リスト
- Graph-Based Correlation Matrix Generation: A Convex Optimization Approach [0.0]
この研究は、グラフ構造に付随する所定の空間パターンを持つ理論的相関行列の生成に対処する。
本稿では,初期行列を正の半定性制約の下で楕円面上に投影する新しい凸最適化フレームワークを提案する。
論文 参考訳(メタデータ) (2026-07-24T15:54:23Z) - Bridging the Gap between Sparse Matrix Reordering and Factorization: A Deep Learning Framework for Fill-in Reduction [8.282571271774573]
スパース行列の並べ替えは、行列分解時のフィインを著しく減少させる。
最小の補充順序を見つけることはNPハード問題であることが知られている。
スペクトル埋め込みに基づく補間関数の最小化を目的としたディープラーニングフレームワークを提案する。
論文 参考訳(メタデータ) (2026-05-17T09:15:42Z) - Recovering Simultaneously Structured Data via Non-Convex Iteratively
Reweighted Least Squares [0.8702432681310401]
線形観測から多種多様低次元構造に固執するデータを復元する新しいアルゴリズムを提案する。
IRLS法は,低/複合状態の計測に好適であることを示す。
論文 参考訳(メタデータ) (2023-06-08T06:35:47Z) - Learning Large Causal Structures from Inverse Covariance Matrix via
Sparse Matrix Decomposition [2.403264213118039]
本稿では,逆共分散行列から因果構造を学習することに焦点を当てる。
提案手法は,行列分解モデルの連続的最適化に基づくICIDと呼ばれる。
本研究では,ノイズ分散の知識を前提として,提案した指向性非巡回グラフ(DAG)を効率よく同定することを示す。
論文 参考訳(メタデータ) (2022-11-25T16:32:56Z) - Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
本稿では,低ランク構造制約下でのグラフ学習のためのフレキシブルなアルゴリズムフレームワークを提案する。
この問題は楕円分布のペナルティ化された最大推定値として表される。
楕円モデルによく適合する正定行列と定ランクの正半定行列のジオメトリを利用する。
論文 参考訳(メタデータ) (2022-10-21T13:19:45Z) - Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
本稿では,初期監視情報を同時に拡張し,識別親和性行列を構築することのできる,新しい半教師付きサブスペースクラスタリング手法を提案する。
6つの一般的なベンチマークデータセットの総合的な実験結果から,本手法が最先端手法よりも優れていることを示す。
論文 参考訳(メタデータ) (2022-05-21T01:47:17Z) - Sparse Quadratic Optimisation over the Stiefel Manifold with Application
to Permutation Synchronisation [71.27989298860481]
二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。
そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-09-30T19:17:35Z) - Robust Low-rank Matrix Completion via an Alternating Manifold Proximal
Gradient Continuation Method [47.80060761046752]
ロバスト低ランク行列補完(RMC)は、コンピュータビジョン、信号処理、機械学習アプリケーションのために広く研究されている。
この問題は、部分的に観察された行列を低ランク行列とスパース行列の重ね合わせに分解することを目的とした。
RMCに取り組むために広く用いられるアプローチは、低ランク行列の核ノルム(低ランク性を促進するために)とスパース行列のl1ノルム(空間性を促進するために)を最小化する凸定式化を考えることである。
本稿では、近年のローワークの動機付けについて述べる。
論文 参考訳(メタデータ) (2020-08-18T04:46:22Z) - Understanding Implicit Regularization in Over-Parameterized Single Index
Model [55.41685740015095]
我々は高次元単一インデックスモデルのための正規化自由アルゴリズムを設計する。
暗黙正則化現象の理論的保証を提供する。
論文 参考訳(メタデータ) (2020-07-16T13:27:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。