論文の概要: Nonlinear Laplacians: Tunable principal component analysis under directional prior information

• arxiv url: http://arxiv.org/abs/2505.12528v1
• Date: Sun, 18 May 2025 19:37:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-20 14:57:11.286577
• Title: Nonlinear Laplacians: Tunable principal component analysis under directional prior information
• Title（参考訳）: 非線形ラプラシアン:方向事前情報に基づく可変主成分分析
• Authors: Yuxin Ma, Dmitriy Kunisky,
• Abstract要約: ノイズの多い観測からランクワン信号を検出し,推定するアルゴリズムを新たに導入する。 直接スペクトルアルゴリズムと比較して,そのようなアルゴリズムの性能について検討する。 理論的にも経験的にも、$sigma$が適切に選択された場合、非線形ラプラシアスペクトルアルゴリズムは直接スペクトルアルゴリズムよりも大幅に優れていることが分かる。
• 参考スコア（独自算出の注目度）: 9.884862296109892
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce a new family of algorithms for detecting and estimating a rank-one signal from a noisy observation under prior information about that signal's direction, focusing on examples where the signal is known to have entries biased to be positive. Given a matrix observation $\mathbf{Y}$, our algorithms construct a nonlinear Laplacian, another matrix of the form $\mathbf{Y} + \mathrm{diag}(\sigma(\mathbf{Y}\mathbf{1}))$ for a nonlinear $\sigma: \mathbb{R} \to \mathbb{R}$, and examine the top eigenvalue and eigenvector of this matrix. When $\mathbf{Y}$ is the (suitably normalized) adjacency matrix of a graph, our approach gives a class of algorithms that search for unusually dense subgraphs by computing a spectrum of the graph "deformed" by the degree profile $\mathbf{Y}\mathbf{1}$. We study the performance of such algorithms compared to direct spectral algorithms (the case $\sigma = 0$) on models of sparse principal component analysis with biased signals, including the Gaussian planted submatrix problem. For such models, we rigorously characterize the critical threshold strength of rank-one signal, as a function of the nonlinearity $\sigma$, at which an outlier eigenvalue appears in the spectrum of a nonlinear Laplacian. While identifying the $\sigma$ that minimizes this critical signal strength in closed form seems intractable, we explore three approaches to design $\sigma$ numerically: exhaustively searching over simple classes of $\sigma$, learning $\sigma$ from datasets of problem instances, and tuning $\sigma$ using black-box optimization of the critical signal strength. We find both theoretically and empirically that, if $\sigma$ is chosen appropriately, then nonlinear Laplacian spectral algorithms substantially outperform direct spectral algorithms, while avoiding the complexity of broader classes of algorithms like approximate message passing or general first order methods.
• Abstract（参考訳）: 本稿では,信号の方向に関する事前情報に基づく雑音観測からランクワン信号を検出し,推定するアルゴリズムを新たに導入する。 行列が $\mathbf{Y}$ を与えられたとき、我々のアルゴリズムは、非線形なラプラシアン(英語版)、つまり $\mathbf{Y} + \mathrm{diag}(\sigma(\mathbf{Y}\mathbf{1}))$ を、非線形な $\sigma: \mathbb{R} \to \mathbb{R}$ に対して構成し、この行列の最高固有値と固有ベクトルを調べる。 $\mathbf{Y}$ がグラフの(好ましくは正規化された)隣接行列であるとき、我々のアプローチは、次数 $\mathbf{Y}\mathbf{1}$ によって「変形」されたグラフのスペクトルを計算することによって、異常に高密度な部分グラフを探索するアルゴリズムのクラスを与える。 ガウス植込み部分行列問題を含む偏波信号を用いたスパース主成分分析モデルにおける直接スペクトルアルゴリズム($\sigma = 0$)と比較して,そのようなアルゴリズムの性能について検討した。 そのようなモデルに対して、ランク1信号の臨界しきい値強度を、非線形ラプラシアンのスペクトルにアウトリー固有値が現れる非線形性$\sigma$の関数として厳密に特徴づける。 クローズドな形でこの臨界信号強度を最小化する$\sigma$を識別する一方で、設計のための3つのアプローチを探求する:$\sigma$の単純なクラスを徹底的に検索し、問題インスタンスのデータセットから$\sigma$を学習し、臨界信号強度のブラックボックス最適化を使用して$\sigma$をチューニングする。 理論的にも経験的にも、$\sigma$が適切に選択された場合、非線形ラプラシアスペクトルアルゴリズムは、近似メッセージパッシングや一般一階法のようなより広範なアルゴリズムのクラスを複雑に回避しながら、直接スペクトルアルゴリズムを著しく上回っていることが分かる。

関連論文リスト

• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• Alternating minimization algorithm with initialization analysis for r-local and k-sparse unlabeled sensing [13.433637831618007]
  実験の結果,提案アルゴリズムは高速で,置換モデルにも適用でき,測定行列の選択にも頑健であることがわかった。 また,リンク線形回帰問題に対して,本アルゴリズムを複数の実データセット上で検証し,ベースライン法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-11-14T18:44:55Z)
• Projected Gradient Descent Algorithms for Solving Nonlinear Inverse Problems with Generative Priors [17.426500577203505]
  未知の$p$次元信号は、有界な$k$次元入力を持つ$L$-Lipschitz連続生成モデルの範囲近くにあると仮定する。 本稿では, 最適統計率を期待できる非線形最小二乗推定器を提案する。
  論文  参考訳（メタデータ） (2022-09-21T04:05:12Z)
• Perturbation Analysis of Randomized SVD and its Applications to High-dimensional Statistics [8.90202564665576]
  一般の「信号+雑音」の枠組みによるRSVDの統計特性について検討する。 3つの統計的推論問題に適用した場合、RSVDのほぼ最適性能保証を導出する。
  論文  参考訳（メタデータ） (2022-03-19T07:26:45Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)
• Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative GLASSO and Projection [58.5350491065936]
  グラフ Laplacian 行列 $L$ 上の構造的仮定を考える。 最初の$K$ eigenvectors of $L$は、例えばドメイン固有の基準に基づいて事前選択される。 本稿では,H_u+$$$$barC$で最も適切なグラフラプラシアン行列$L*を計算するために,効率的なハイブリッドグラフラッソ/投影アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-10-25T18:12:50Z)
• Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
  ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。 我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-09-30T19:10:32Z)
• Learning nonlinear dynamical systems from a single trajectory [102.60042167341956]
  我々は、$x_t+1=sigma(Thetastarx_t)+varepsilon_t$という形の非線形力学系を学ぶアルゴリズムを導入する。 最適なサンプル複雑性と線形ランニング時間を持つ単一軌道から重み行列$Thetastar$を復元するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-30T10:42:48Z)

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

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