論文の概要: Consistent Multigroup Low-Rank Approximation
- arxiv url: http://arxiv.org/abs/2503.21563v1
- Date: Thu, 27 Mar 2025 14:47:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-28 12:54:31.334138
- Title: Consistent Multigroup Low-Rank Approximation
- Title(参考訳): 一貫性多群低ランク近似
- Authors: Antonis Matakos, Martino Ciaperoni, Heikki Mannila,
- Abstract要約: マルチグループデータに対する一貫した低ランク近似の問題を考察する。
最良の階数(1$プロジェクション)を見つけるには、原始双対アプローチや半有限計画法を用いる。
- 参考スコア(独自算出の注目度): 2.5056643038238504
- License:
- Abstract: We consider the problem of consistent low-rank approximation for multigroup data: we ask for a sequence of $k$ basis vectors such that projecting the data onto their spanned subspace treats all groups as equally as possible, by minimizing the maximum error among the groups. Additionally, we require that the sequence of basis vectors satisfies the natural consistency property: when looking for the best $k$ vectors, the first $d<k$ vectors are the best possible solution to the problem of finding $d$ basis vectors. Thus, this multigroup low-rank approximation method naturally generalizes \svd and reduces to \svd for data with a single group. We give an iterative algorithm for this task that sequentially adds to the basis the vector that gives the best rank$-1$ projection according to the min-max criterion, and then projects the data onto the orthogonal complement of that vector. For finding the best rank$-1$ projection, we use primal-dual approaches or semidefinite programming. We analyze the theoretical properties of the algorithms and demonstrate empirically that the proposed methods compare favorably to existing methods for multigroup (or fair) PCA.
- Abstract(参考訳): 多重群データに対する一貫した低ランク近似の問題を考察し、各群間の最大誤差を最小限に抑えて、その部分空間にデータを射影するような$k$基底ベクトル列を求める。
さらに、基底ベクトルの列は自然な整合性を満たすことを要求する: 最高の$k$ベクトルを求めるとき、最初の$d<k$ベクトルは、$d$基底ベクトルを見つける問題に対する最良の解である。
したがって、この多群ローランク近似法は自然に \svd を一般化し、単一の群を持つデータに対して \svd に還元する。
このタスクに対して反復アルゴリズムを与え、min-max基準に従って最良の階数1$プロジェクションを与えるベクトルを逐次加算し、そのベクトルの直交補数にデータを投影する。
最良の階数(1$プロジェクション)を見つけるには、原始双対アプローチや半有限計画法を用いる。
提案手法は,提案手法が既存のマルチグループ(またはフェア)PCA法と良好に比較できることを実証的に示す。
関連論文リスト
- SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More [37.208622097149714]
我々は、最大$|M u|$で境界を証明できる新しいアップタイムアルゴリズムの族を与える。
我々の認証アルゴリズムは, Sum-of-Squares階層を必須に活用する。
論文 参考訳(メタデータ) (2024-12-30T18:59:46Z) - Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
クラウドソーシングによって動機づけられた我々は、$d$の質問に対する$n$の専門家の回答の正しさを部分的に観察する問題を考える。
本稿では、専門家$i$が疑問に答える確率を含む行列$M$が、行と列の置換までの双等方性であることを仮定する。
我々は,この分類問題に対して最小限のアルゴリズムを最適に構築する。
論文 参考訳(メタデータ) (2024-08-27T18:28:31Z) - Optimal Bound for PCA with Outliers using Higher-Degree Voronoi Diagrams [0.0]
本稿では,主成分分析 (PCA) のための新しいアルゴリズムについて紹介する。
外れ値が存在する場合でも、PCAの最適部分空間にナビゲートする。
このアプローチは、$nd+mathcalO(1)textpoly(n,d)$の時間複雑性を持つ最適解を得る。
論文 参考訳(メタデータ) (2024-08-13T13:05:36Z) - Efficient Algorithms for Empirical Group Distributional Robust
Optimization and Beyond [15.664414751701718]
経験的GDROを$textittwo-level$ finite-sum convex-concave minimax Optimization問題として定式化する。
我々は、スナップショットとミラースナップショットポイントを1インデックスシフトした重み付き平均で計算し、単純エルゴディック平均と区別する。
注目すべきは、我々の手法が最先端の手法よりも$sqrtm$で優れていることだ。
論文 参考訳(メタデータ) (2024-03-06T09:14:24Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳(メタデータ) (2022-08-11T04:12:50Z) - Optimal N-ary ECOC Matrices for Ensemble Classification [1.3561997774592662]
アンサンブル分類法における誤り訂正出力符号(ECOC)の新たな構成について述べる。
任意の素数$N$が与えられたとき、この決定論的構成は基底-$N$対称二乗行列を$M$で生成する。
論文 参考訳(メタデータ) (2021-10-05T16:50:15Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-06-16T03:34:14Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳(メタデータ) (2021-06-04T02:32:26Z) - Hutch++: Optimal Stochastic Trace Estimation [75.45968495410048]
我々は、任意の正半定値(PSD)$A$に対して、$(1 pm epsilon)$を$tr(A)$に近似する新しいランダム化アルゴリズムであるHutch++を導入する。
実験ではハッチンソン法を著しく上回る結果を得た。
論文 参考訳(メタデータ) (2020-10-19T16:45:37Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳(メタデータ) (2020-02-26T16:19:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。