論文の概要: Support Recovery of Sparse Signals from a Mixture of Linear Measurements

• arxiv url: http://arxiv.org/abs/2106.05951v1
• Date: Thu, 10 Jun 2021 17:48:13 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-11 14:27:43.538223
• Title: Support Recovery of Sparse Signals from a Mixture of Linear Measurements
• Title（参考訳）: 線形計測値の混合によるスパース信号の回復支援
• Authors: Venkata Gandikota, Arya Mazumdar, Soumyabrata Pal
• Abstract要約: 簡単な測定からスパースベクトルの支持を回復することは、広く研究されている問題である。 この問題の一般化を考える:線形回帰の混合と線形分類器の混合である。 我々は$k, log n$ および quasi-polynomial を $ell$ で多くの測定値を用いて、混合中の未知ベクトルの全てのサポートを回復するアルゴリズムを提供する。
• 参考スコア（独自算出の注目度）: 48.556633593447465
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recovery of support of a sparse vector from simple measurements is a widely studied problem, considered under the frameworks of compressed sensing, 1-bit compressed sensing, and more general single index models. We consider generalizations of this problem: mixtures of linear regressions, and mixtures of linear classifiers, where the goal is to recover supports of multiple sparse vectors using only a small number of possibly noisy linear, and 1-bit measurements respectively. The key challenge is that the measurements from different vectors are randomly mixed. Both of these problems were also extensively studied recently. In mixtures of linear classifiers, the observations correspond to the side of queried hyperplane a random unknown vector lies in, whereas in mixtures of linear regressions we observe the projection of a random unknown vector on the queried hyperplane. The primary step in recovering the unknown vectors from the mixture is to first identify the support of all the individual component vectors. In this work, we study the number of measurements sufficient for recovering the supports of all the component vectors in a mixture in both these models. We provide algorithms that use a number of measurements polynomial in $k, \log n$ and quasi-polynomial in $\ell$, to recover the support of all the $\ell$ unknown vectors in the mixture with high probability when each individual component is a $k$-sparse $n$-dimensional vector.
• Abstract（参考訳）: 単純な測定からスパースベクトルのサポートを回復することは、圧縮センシング、1ビット圧縮センシング、より一般的なシングルインデックスモデルの枠組みで検討された広く研究されている問題である。 線形回帰の混合と線形分類器の混合というこの問題の一般化を考察し、そこでは、少数個のノイズのある線形と1ビットの測定だけを用いて、複数のスパースベクトルのサポートを回復することが目的である。 鍵となる課題は、異なるベクトルからの測定がランダムに混合されることである。 どちらの問題も近年広く研究されている。 線形分類器の混合では、この観測は列状超平面の側面にランダムな未知ベクトルが存在するのに対し、線形回帰の混合では、列状超平面上のランダムな未知ベクトルの投影を観察する。 混合から未知のベクトルを回収する第一のステップは、まず個々の成分ベクトルの支持を識別することである。 本研究では,両モデルにおける混合成分ベクトルの支持部を回収するのに十分な測定数について検討する。 我々は、各成分がk$-sparse $n$-dimensional ベクトルである場合、混合中のすべての$\ell$ 未知ベクトルのサポートを高い確率で回復するために、いくつかの測定多項式を $k, \log n$ および pseudo-polynomial で$\ell$で使用するアルゴリズムを提供する。

関連論文リスト

• Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexity [11.412228884390784]
  いくつかの測定値から低ランク2次凸行列を再構成する問題について検討した。 スペクトル特異性を持つ分解勾配は標本数と真理に収束することを示す。
  論文  参考訳（メタデータ） (2024-08-20T14:09:28Z)
• Precise Asymptotics for Spectral Methods in Mixed Generalized Linear Models [31.58736590532443]
  混合一般化線形モデルにおいて、統計的に独立な2つの信号を推定する問題を考える。 我々の特徴付けは、ランダム行列、自由確率、および近似メッセージパッシングアルゴリズムの理論からのツールの混合を利用する。
  論文  参考訳（メタデータ） (2022-11-21T11:35:25Z)
• Sparse Mixed Linear Regression with Guarantees: Taming an Intractable Problem with Invex Relaxation [31.061339148448006]
  本稿では,ラベルのないデータセット上での疎混合線形回帰問題について検討する。 我々は、この難解な問題に対して、証明可能な理論的保証を持つ解をもたらす新しい凸緩和を提供する。
  論文  参考訳（メタデータ） (2022-06-02T17:38:11Z)
• On Learning Mixture Models with Sparse Parameters [44.3425205248937]
  本研究では, 高次元スパルス潜時パラメータベクトルの混合について検討し, これらのベクトルの回復支援問題について考察する。 潜伏空間の次元に対数的サンプル複雑性が依存する回復支援のための効率的なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-02-24T07:44:23Z)
• When Random Tensors meet Random Matrices [50.568841545067144]
  本稿では,ガウス雑音を伴う非対称次数-$d$スパイクテンソルモデルについて検討する。 検討したモデルの解析は、等価なスパイクされた対称テクシットブロック-ワイドランダム行列の解析に起因していることを示す。
  論文  参考訳（メタデータ） (2021-12-23T04:05:01Z)
• Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priors [54.936314353063494]
  我々は,ロバストな1ビット圧縮センシングのための相関に基づく最適化アルゴリズムのリカバリ保証を提供する。 我々は,実用的な反復アルゴリズムを用いて,画像データセットの数値実験を行い,結果の相関付けを行う。
  論文  参考訳（メタデータ） (2021-08-08T05:28:06Z)
• Analysis of Truncated Orthogonal Iteration for Sparse Eigenvector Problems [78.95866278697777]
  本研究では,多元的固有ベクトルを分散制約で同時に計算するTruncated Orthogonal Iterationの2つの変種を提案する。 次に,我々のアルゴリズムを適用して,幅広いテストデータセットに対するスパース原理成分分析問題を解く。
  論文  参考訳（メタデータ） (2021-03-24T23:11:32Z)
• Recovery of sparse linear classifiers from mixture of responses [42.228977798395846]
  双対応答列から超平面の集合を学習する方法を示す。 各応答はベクトルとのクエリの結果であり、クエリベクトルが属するコレクションからランダムに選択された超平面の側面を示す。
  論文  参考訳（メタデータ） (2020-10-22T22:03:53Z)
• 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)
• Semiparametric Nonlinear Bipartite Graph Representation Learning with Provable Guarantees [106.91654068632882]
  半パラメトリック指数族分布におけるパラメータの統計的推定問題として、両部グラフを考察し、その表現学習問題を定式化する。 提案手法は, 地中真理付近で強い凸性を示すため, 勾配降下法が線形収束率を達成できることを示す。 我々の推定器は指数族内の任意のモデル誤特定に対して頑健であり、広範な実験で検証されている。
  論文  参考訳（メタデータ） (2020-03-02T16:40:36Z)

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

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