論文の概要: Spiky Rank and Its Applications to Rigidity and Circuits

• arxiv url: http://arxiv.org/abs/2602.23503v1
• Date: Thu, 26 Feb 2026 21:20:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-02 19:48:24.132792
• Title: Spiky Rank and Its Applications to Rigidity and Circuits
• Title（参考訳）: スパイクランクと剛性・回路への応用
• Authors: Lianna Hambardzumyan, Konstantin Myasnikov, Artur Riazanov, Morgan Shirley, Adi Shraibman,
• Abstract要約: スパイキーランクは新しい行列パラメータで、後者の構造と線形代数的柔軟性を組み合わせることでブロッキーランクを高める。 本研究では,大きなスパイクランクは高い行列剛性を示し,そのスパイクランクの下限は深さ2ReLU回路の下位境界となることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce spiky rank, a new matrix parameter that enhances blocky rank by combining the combinatorial structure of the latter with linear-algebraic flexibility. A spiky matrix is block-structured with diagonal blocks that are arbitrary rank-one matrices, and the spiky rank of a matrix is the minimum number of such matrices required to express it as a sum. This measure extends blocky rank to real matrices and is more robust for problems with both combinatorial and algebraic character. Our conceptual contribution is as follows: we propose spiky rank as a well-behaved candidate matrix complexity measure and demonstrate its potential through applications. We show that large spiky rank implies high matrix rigidity, and that spiky rank lower bounds yield lower bounds for depth-2 ReLU circuits, the basic building blocks of neural networks. On the technical side, we establish tight bounds for random matrices and develop a framework for explicit lower bounds, applying it to Hamming distance matrices and spectral expanders. Finally, we relate spiky rank to other matrix parameters, including blocky rank, sparsity, and the $γ_2$-norm.
• Abstract（参考訳）: 本稿では,後者の組合せ構造と線形代数的柔軟性を組み合わせることで,ブロックランクを高める新しい行列パラメータであるスパイキーランクを導入する。 スパイキー行列は任意のランク1行列である対角ブロックでブロック構造され、マトリクスのスパイキーランクは、それを和として表現するのに必要となるそのような行列の最小数である。 この測度はブロッキーランクを実行列に拡張し、組合せ的および代数的キャラクタの問題に対してより堅牢である。 我々の概念的コントリビューションは以下の通りである: 良好に達成された候補行列の複雑性尺度としてスパイクランクを提案し、応用を通してそのポテンシャルを実証する。 本研究では,大きなスパイクランクは高い行列剛性を示し,スパイクランクの下限はニューラルネットワークの基本構成ブロックであるディープ-2 ReLU回路の下位境界となることを示す。 技術的には、ランダム行列の厳密な境界を確立し、ハミング距離行列とスペクトル展開器に適用し、明示的な下界の枠組みを開発する。 最後に、ブロッキーランク、スパシティ、および$γ_2$-normを含む他の行列パラメータにスパイクランクを関連付ける。

関連論文リスト

• Spectral Estimation with Free Decompression [47.81955761814048]
  非常に大きな(可逆な)行列のスペクトルを推定する「自由減圧」の新たな手法を提案する。 提案手法は, 極大(非可逆)行列の固有スペクトルを推定するために, 小型サブマトリクスの実験的スペクトル密度から外挿することができる。
  論文  参考訳（メタデータ） (2025-06-13T17:49:25Z)
• Cramer-Rao Bounds for Laplacian Matrix Estimation [56.1214184671173]
  クラマー・ラオ境界(CRB)の閉形式行列式をラプラシア行列推定に特化して導出した。 電力系統における(i)トポロジー同定,(ii)拡散モデルにおけるグラフフィルタ同定,(iii)ラプラシアン制約下でのガウスマルコフ確率場における精度行列推定の3つの代表的応用について示す。
  論文  参考訳（メタデータ） (2025-04-06T18:28:31Z)
• Controlled measurement, Hermitian conjugation and normalization in matrix-manipulation algorithms [46.13392585104221]
  本稿では,小アクセス確率を所望のアシラ状態に限定する制御計測の概念を提案する。 複素行列の実部と虚部の分離符号化は、エルミート共役を行列操作のリストに含めることができる。 純粋量子状態の正規化条件によって必然的に課される行列要素の絶対値の制約を弱める。
  論文  参考訳（メタデータ） (2025-03-27T08:49:59Z)
• Semi-supervised Symmetric Non-negative Matrix Factorization with Low-Rank Tensor Representation [27.14442336413482]
  半教師付き対称非負行列分解(SNMF) 対制約行列により合成されたテンソルの低ランク表現を求めるSNMFモデルを提案する。 次に、拡張SNMFモデルを提案し、埋め込み行列を上記のテンソル低ランク表現に適合させる。
  論文  参考訳（メタデータ） (2024-05-04T14:58:47Z)
• Factor Fitting, Rank Allocation, and Partitioning in Multilevel Low Rank Matrices [39.594033761023695]
  フロベニウスノルムの MLR 行列によって与えられた行列を適合させる際に生じる3つの問題に対処する。 第一の問題は、MLR行列の因子を調整する因子フィッティングである。 2つ目はランクアロケーションで、各レベルにおけるブロックのランクを、与えられた値の合計ランクに基づいて選択する。 最終問題は、列と列の階層的な分割と、ランクと要素を選択することである。
  論文  参考訳（メタデータ） (2023-10-30T00:52:17Z)
• Mutually-orthogonal unitary and orthogonal matrices [6.9607365816307]
  実2重項系における拡張不可能な最大絡み合い基底の最小値と最大値はそれぞれ3と4であることを示す。 量子情報理論の応用として、実2量子系内の最大エンタングル基底の最小値と最大値はそれぞれ3と4であることを示す。
  論文  参考訳（メタデータ） (2023-09-20T08:20:57Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  本稿では,初期監視情報を同時に拡張し,識別親和性行列を構築することのできる,新しい半教師付きサブスペースクラスタリング手法を提案する。 6つの一般的なベンチマークデータセットの総合的な実験結果から,本手法が最先端手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-05-21T01:47:17Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  非PSDおよび2乗根行列の次元削減法を提案する。 複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2021-06-16T04:07:48Z)
• On the Optimality of Nuclear-norm-based Matrix Completion for Problems with Smooth Non-linear Structure [19.069068837749885]
  行列完備化は、下層の行列に低次元線型構造を仮定する理由がない多くの問題において広く有効であることが証明されている。 原子核のペナライゼーションは、観測がランダムに完全に欠けている場合にこれらの行列を回復するのに有効であることを示す。
  論文  参考訳（メタデータ） (2021-05-05T05:34:32Z)
• Robust Low-rank Matrix Completion via an Alternating Manifold Proximal Gradient Continuation Method [47.80060761046752]
  ロバスト低ランク行列補完(RMC)は、コンピュータビジョン、信号処理、機械学習アプリケーションのために広く研究されている。 この問題は、部分的に観察された行列を低ランク行列とスパース行列の重ね合わせに分解することを目的とした。 RMCに取り組むために広く用いられるアプローチは、低ランク行列の核ノルム(低ランク性を促進するために)とスパース行列のl1ノルム(空間性を促進するために)を最小化する凸定式化を考えることである。 本稿では、近年のローワークの動機付けについて述べる。
  論文  参考訳（メタデータ） (2020-08-18T04:46:22Z)
• Relative Error Bound Analysis for Nuclear Norm Regularized Matrix Completion [101.83262280224729]
  我々は、原子核ノルム正規化行列補完に対する相対誤差を開発する。 未知行列の最適低ランク近似を回復するための相対上界を導出する。
  論文  参考訳（メタデータ） (2015-04-26T13:12:16Z)

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

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