論文の概要: Computationally Efficient Approximations for Matrix-based Renyi's
Entropy
- arxiv url: http://arxiv.org/abs/2112.13720v1
- Date: Mon, 27 Dec 2021 14:59:52 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-28 14:38:11.237913
- Title: Computationally Efficient Approximations for Matrix-based Renyi's
Entropy
- Title（参考訳）: 行列ベース Renyi のエントロピーに対する計算効率の良い近似法
- Authors: Tieliang Gong and Yuxin Dong and Shujian Yu and Hong Chen and Bo Dong
and Chen Li and Qinghua Zheng
- Abstract要約: 最近開発された行列ベースのRenyiのエントロピーは、データ内の情報の計測を可能にする。
そのような量の計算には、PSD行列の$G$上のトレース演算子を$alpha$(つまり$tr(Galpha)$)の電力とする。
我々は、この新しいエントロピー汎函数に対する計算学的に効率的な近似を示し、その複雑性を$O(n2)$よりもはるかに小さくすることができる。
- 参考スコア（独自算出の注目度）: 33.72108955447222
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The recently developed matrix based Renyi's entropy enables measurement of
information in data simply using the eigenspectrum of symmetric positive semi
definite (PSD) matrices in reproducing kernel Hilbert space, without estimation
of the underlying data distribution. This intriguing property makes the new
information measurement widely adopted in multiple statistical inference and
learning tasks. However, the computation of such quantity involves the trace
operator on a PSD matrix $G$ to power $\alpha$(i.e., $tr(G^\alpha)$), with a
normal complexity of nearly $O(n^3)$, which severely hampers its practical
usage when the number of samples (i.e., $n$) is large. In this work, we present
computationally efficient approximations to this new entropy functional that
can reduce its complexity to even significantly less than $O(n^2)$. To this
end, we first develop randomized approximations to $\tr(\G^\alpha)$ that
transform the trace estimation into matrix-vector multiplications problem. We
extend such strategy for arbitrary values of $\alpha$ (integer or non-integer).
We then establish the connection between the matrix-based Renyi's entropy and
PSD matrix approximation, which enables us to exploit both clustering and block
low-rank structure of $\G$ to further reduce the computational cost. We
theoretically provide approximation accuracy guarantees and illustrate the
properties of different approximations. Large-scale experimental evaluations on
both synthetic and real-world data corroborate our theoretical findings,
showing promising speedup with negligible loss in accuracy.
- Abstract（参考訳）: 最近開発されたRenyiのエントロピーは、基盤となるデータ分布を推定することなく、カーネルヒルベルト空間を再現する対称正半定値行列の固有スペクトルを用いてデータ中の情報を測定することができる。
この興味深い性質は、複数の統計的推論および学習タスクにおいて、新しい情報測定を広く採用する。
しかし、そのような量の計算には、PSD行列の$G$上のトレース作用素が$\alpha$(すなわち$tr(G^\alpha)$)を出力し、通常の複雑さは$O(n^3)$に近くなり、サンプル数(すなわち$n$)が大きければその実用的利用を著しく損なう。
本研究では,この新しいエントロピー関数を計算効率良く近似し,その複雑性を最大で$o(n^2)$ 以下まで低減する手法を提案する。
この目的のために、まずランダム化近似を$\tr(\G^\alpha)$に発展させ、トレース推定を行列ベクトル乗法問題に変換する。
そのような戦略を$\alpha$(整数または非整数)の任意の値に対して拡張する。
次に、行列ベースのRenyiのエントロピーとPSD行列近似の接続を確立することにより、クラスタリングと$\G$の低ランク構造の両方を利用でき、計算コストをさらに削減できる。
理論的には近似精度保証を提供し、異なる近似の特性を示す。
合成データと実世界のデータの両方に関する大規模な実験的評価は、理論的な結果と相関し、精度の低下を無視できるスピードアップを示す。
関連論文リスト
- Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳（メタデータ） (2024-03-08T18:50:19Z) - Effective Minkowski Dimension of Deep Nonparametric Regression: Function
Approximation and Statistical Theories [70.90012822736988]
ディープ非パラメトリック回帰に関する既存の理論は、入力データが低次元多様体上にある場合、ディープニューラルネットワークは本質的なデータ構造に適応できることを示した。
本稿では,$mathcalS$で表される$mathbbRd$のサブセットに入力データが集中するという緩和された仮定を導入する。
論文 参考訳（メタデータ） (2023-06-26T17:13:31Z) - Robust and Fast Measure of Information via Low-rank Representation [20.1194871649588]
我々は低ランク行列に基づくR'enyiのエントロピーと呼ばれる新しい情報尺度を提案する。
低ランク変種は、基底分布の変化によって引き起こされる情報的摂動に対してより敏感である。
我々は,この新たな情報尺度の有効性を評価するため,大規模な実験を行った。
論文 参考訳（メタデータ） (2022-11-30T06:49:56Z) - Optimal Randomized Approximations for Matrix based Renyi's Entropy [16.651155375441796]
整数次数$alpha$の場合のランダム近似と非整数$alpha$の場合の直列近似を開発する。
大規模シミュレーションと実世界の応用は、開発した近似の有効性を検証する。
論文 参考訳（メタデータ） (2022-05-16T02:24:52Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳（メタデータ） (2022-02-23T16:10:23Z) - Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature
Selection [138.97647716793333]
再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。
提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
論文 参考訳（メタデータ） (2020-12-29T04:08:38Z) - Fast and Accurate Pseudoinverse with Sparse Matrix Reordering and
Incremental Approach [4.710916891482697]
擬逆は行列逆の一般化であり、機械学習で広く利用されている。
FastPIはスパース行列に対する新たなインクリメンタル特異値分解法(SVD)である。
我々は,FastPIが精度を損なうことなく,他の近似手法よりも高速に擬似逆計算を行うことを示す。
論文 参考訳（メタデータ） (2020-11-09T07:47:10Z) - Hutch++: Optimal Stochastic Trace Estimation [75.45968495410048]
我々は、任意の正半定値(PSD)$A$に対して、$(1 pm epsilon)$を$tr(A)$に近似する新しいランダム化アルゴリズムであるHutch++を導入する。
実験ではハッチンソン法を著しく上回る結果を得た。
論文 参考訳（メタデータ） (2020-10-19T16:45:37Z) - Compressed sensing of low-rank plus sparse matrices [3.8073142980733]
この写本は、ランクラパース行列と$sスパース行列の和として表現できる$mtimes n$が計算的に抽出可能な方法で復元可能であることを示す同様の保証を開発する。
その結果, 合成問題, 動的地上/静電分離, マルチスペクトルイメージング, ロバストPCAが得られた。
論文 参考訳（メタデータ） (2020-07-18T15:36:11Z) - Phase retrieval in high dimensions: Statistical and computational phase
transitions [27.437775143419987]
我々は$mathbfXstar$を$m$(おそらくノイズの多い)観測から再構成する問題を考察する。
特に、フルランク行列に対する情報理論上の完全回復への遷移は、$alpha=1$と$alpha=2$である。
我々の研究は、高次元位相探索における統計的およびアルゴリズム的しきい値の広範な分類を提供する。
論文 参考訳（メタデータ） (2020-06-09T13:03:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。