論文の概要: Constructing fast approximate eigenspaces with application to the fast graph Fourier transforms

• arxiv url: http://arxiv.org/abs/2002.09723v3
• Date: Tue, 18 May 2021 20:32:41 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-29 19:19:35.448230
• Title: Constructing fast approximate eigenspaces with application to the fast graph Fourier transforms
• Title（参考訳）: 高速近似固有空間の構築と高速グラフフーリエ変換への応用
• Authors: Cristian Rusu and Lorenzo Rosasco
• Abstract要約: 本研究では,対称行列および一般行列に付随する固有空間の数値的に効率的な近似について検討する。 固有空間は、効率的に操作できる固定数の基本成分に分解される。 ランダムな行列に関する結果と、有向グラフおよび無向グラフに対するグラフフーリエ変換の近似への応用を示す。
• 参考スコア（独自算出の注目度）: 20.06200814131424
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate numerically efficient approximations of eigenspaces associated to symmetric and general matrices. The eigenspaces are factored into a fixed number of fundamental components that can be efficiently manipulated (we consider extended orthogonal Givens or scaling and shear transformations). The number of these components controls the trade-off between approximation accuracy and the computational complexity of projecting on the eigenspaces. We write minimization problems for the single fundamental components and provide closed-form solutions. Then we propose algorithms that iterative update all these components until convergence. We show results on random matrices and an application on the approximation of graph Fourier transforms for directed and undirected graphs.
• Abstract（参考訳）: 対称行列および一般行列に付随する固有空間の数値的効率的な近似について検討する。 固有空間は、効率よく操作できる基本成分の固定個数に分解される(拡張直交の命題やスケーリングやせん断変換を考える)。 これらの成分の数は、近似精度と固有空間上の投影の計算複雑性の間のトレードオフを制御する。 単一基本成分の最小化問題を書き、閉形式解を提供する。 次に,これらすべてのコンポーネントを収束するまで反復的に更新するアルゴリズムを提案する。 ランダム行列に関する結果と、有向グラフおよび無向グラフに対するグラフフーリエ変換の近似への応用を示す。

関連論文リスト

• Stochastic Parallelizable Eigengap Dilation for Large Graph Clustering [12.544602297450533]
  私たちは、ほとんどのエッジがクラスタ内に落ち、わずかにエッジがクラスタ間に落ちているノードのクラスタを特定することを目的としています。 スペクトルクラスタリングのコアステップは、対応するグラフラプラシア行列の固有分解を行う。 本稿では,SVDソルバを高速化し,スペクトルクラスタリングを行うために,スペクトルを並列化可能なアプローチを提案する。
  論文  参考訳（メタデータ） (2022-07-29T10:13:07Z)
• Alternating Mahalanobis Distance Minimization for Stable and Accurate CP Decomposition [4.847980206213335]
  本稿では, テンソルの特異値とベクトルを導出するための新しい定式化を導入する。 このアルゴリズムのサブスウィープは、既知のランクの正確なCPDに対して超線形収束率を達成することができることを示す。 すると、アルゴリズムは各因子に対するマハラノビス距離を最適化するものであり、基底距離は他の因子に依存していると見なす。
  論文  参考訳（メタデータ） (2022-04-14T19:56:36Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。 そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-30T19:17:35Z)
• Analysis of Truncated Orthogonal Iteration for Sparse Eigenvector Problems [78.95866278697777]
  本研究では,多元的固有ベクトルを分散制約で同時に計算するTruncated Orthogonal Iterationの2つの変種を提案する。 次に,我々のアルゴリズムを適用して,幅広いテストデータセットに対するスパース原理成分分析問題を解く。
  論文  参考訳（メタデータ） (2021-03-24T23:11:32Z)
• Square Root Bundle Adjustment for Large-Scale Reconstruction [56.44094187152862]
  QR分解によるランドマーク変数のnullspace marginalizationに依存するバンドル調整問題の新たな定式化を提案する。 平方根束調整と呼ばれる私たちのアプローチは、一般的に使用されるSchur補完トリックと代数的に等価です。 BALデータセットを用いた実世界での実験では、提案されたソルバが単一の精度でも平均的等しく正確なソリューションで達成できることを示す。
  論文  参考訳（メタデータ） (2021-03-02T16:26:20Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。 まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。 次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-01-19T04:24:23Z)
• Communication-efficient distributed eigenspace estimation [31.69089186688224]
  我々は,データ行列の先頭不変部分空間を計算するための通信効率のよい分散アルゴリズムを開発した。 提案アルゴリズムは局所解と参照解の間のプロクリスト距離を最小化する新しいアライメント方式を用いる。 本アルゴリズムは,集中型推定器と同様の誤差率を示す。
  論文  参考訳（メタデータ） (2020-09-05T02:11:22Z)
• Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations [59.84561168501493]
  最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。 驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。 提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
  論文  参考訳（メタデータ） (2020-08-12T08:52:50Z)
• Spectral Learning on Matrices and Tensors [74.88243719463053]
  テンソル分解は行列法で欠落する潜伏効果を拾うことができることを示す。 また,効率的なテンソル分解法を設計するための計算手法についても概説する。
  論文  参考訳（メタデータ） (2020-04-16T22:53:00Z)
• Dynamical perturbation theory for eigenvalue problems [0.0]
  提案アルゴリズムは,通常のレイリー=シュル・オーディンガー展開を3つの数で上回ることを示す。 また,本手法は汎用固有値ルーチンよりも行列のサイズがよい。
  論文  参考訳（メタデータ） (2020-02-28T17:13:22Z)

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

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