(57)【特許請求の範囲】
【請求項１】
ストリーミングデータの圧縮センシングを実行する方法であって、
データの入力ストリームにおいてオーバーラップするウィンドウのためのセンシング行列Ａのシーケンスを再帰的に選択することと、第（ｉ＋２）のオーバーラップするウィンドウのための前記センシング行列Ａ(ｉ＋１)は、式Ａ（ｉ＋１）＝［ａ２（ｉ）,ａ３（ｉ）, . . . , ａｎ（ｉ）, ａ１（ｉ）］によって定義され、ここで、ａＬ（ｉ）は、前記センシング行列Ａ(ｉ)の第Ｌ列であり、ｎは各オーバーラップするウィンドウの長さであり、ｉは０以上であり、
式ｙ（ｉ＋１）＝ｙ（ｉ）＋（ｘｉ＋ｎ-ｘｉ）ａ１（ｉ）を使用して、前記第（ｉ＋２）のオーバーラップするウィンドウのための測定値ｙ（ｉ＋１）を取得することと、ここで、ｉは０以上であり、第（ｉ＋１）のオーバーラップするウィンドウに対応するデータの前記入力ストリームの信号ｘ（ｉ）は、式ｘ（ｉ）＝［ｘｉ ｘｉ＋１ . . . ｘｉ＋ｎ−１］によって定義され、最初のオーバーラップするウィンドウのための前記測定値ｙ（０）は、式ｙ（０）＝Ａ（０）ｘ（０）によって定義される、
に少なくとも部分的によって、データの入力ストリームを、連続するオーバーラップするウィンドウを使用して再帰的にサンプリングすること
を備える、方法。
【請求項２】
前記測定値ｙ（ｉ＋１）を取得する前記ステップは、前記センシング行列Ａのうちの１つを含む行列乗算を実行することなく実行される、請求項１に記載のストリーミングデータの圧縮センシングを実行するための方法。
【請求項３】
前記測定値ｙ（ｉ）を取得する前記ステップは、データの前記入力ストリームを再帰的にサンプリングするステップの間にサンプリングされたデータを、再帰的な推定を介して、処理することを備える、請求項１に記載のストリーミングデータの圧縮センシングを実行するための方法。
【請求項４】
前記入力データストリームに関する情報を受信することをさらに備え、ここにおいて、前記情報は、以前の推定値取得ステップの間に取得された以前の推定値に関係し、前記以前の推定値取得ステップは、前記再帰的なサンプリングステップの前に実行される、
請求項３に記載のストリーミングデータの圧縮センシングを実行するための方法。
【請求項５】
データストリームを検出することと、
前記データストリーム検出ステップの間に取得される情報に基づいて、回数推定を実行することと
をさらに備える、請求項３に記載のストリーミングデータの圧縮センシングを実行するための方法。
【請求項６】
前記再帰的な推定ステップの間に取得されるデータに基づいて、データストリームの集合に対して最小２乗推定（ＬＳＥ）値を算出することをさらに備える、請求項３に記載のストリーミングデータの圧縮センシングを実行するための方法。
【請求項７】
平均された値を算出するために、前記算出された最小２乗推定値と、前記回数推定値と、前記以前の推定値とを平均することをさらに備える、請求項６に記載のストリーミングデータの圧縮センシングを実行するための方法。
【請求項８】
前記ストリーミングデータに対する新しい推定値を取得するために、前記平均された値を使用することをさらに備える、請求項７に記載のストリーミングデータの圧縮センシングを実行するための方法。
【請求項９】
ストリーミングデータの前記圧縮センシングの計算量を分析することをさらに備える、請求項１に記載のストリーミングデータの圧縮センシングを実行するための方法。
【請求項１０】
ストリーミングデータを感知するための前記方法の誤差の程度を推定することをさらに備える、請求項９に記載のストリーミングデータの圧縮センシングを実行するための方法。
【請求項１１】
前記連続するオーバーラップするウィンドウから取得される信号推定値を平均することをさらに備え、ここにおいて、ストリーミングデータの圧縮センシングを実行することは、
集合検出を実行することと、
信号振幅推定と
を備える、請求項１に記載のストリーミングデータの圧縮センシングを実行するための方法。
【請求項１２】
大きい測定雑音の存在下で、ロバストな推定のために投票方式を適用することをさらに備える、請求項１に記載のストリーミングデータの圧縮センシングを実行するための方法。
【請求項１３】
記録されたプログラムを有するコンピュータ可読記憶媒体であって、前記プログラムは、コンピュータに請求項１乃至１２のうちの一項に記載の方法を実行させる、コンピュータ可読記憶媒体。
【請求項１４】
ストリーミングデータの圧縮センシングを実行するための装置であって、
センサデータの入力ストリームからのデータを記憶するように構成されたメモリと、
プロセッサと
を備え、前記プロセッサは、
センサデータの入力ストリームにおいてオーバーラップするウィンドウのためのセンシング行列Ａのシーケンスを再帰的に選択することと、第（ｉ＋２）のオーバーラップするウィンドウのための前記センシング行列Ａ(ｉ＋１)は、式Ａ（ｉ＋１）＝［ａ２（ｉ）,ａ３（ｉ）, . . . , ａｎ（ｉ）, ａ１（ｉ）］によって定義され、ここで、ａＬ（ｉ）は、前記センシング行列Ａ(ｉ)の第Ｌ列であり、ｎは各オーバーラップするウィンドウの長さであり、ｉは０以上であり、
式ｙ（ｉ＋１）＝ｙ（ｉ）＋（ｘｉ＋ｎ-ｘｉ）ａ１（ｉ）を使用して、前記第（ｉ＋２）のオーバーラップするウィンドウのための測定値ｙ（ｉ＋１）を取得することと、ここで、ｉは０以上であり、第（ｉ＋１）のオーバーラップするウィンドウに対応するセンサデータの前記入力ストリームの信号ｘ（ｉ）は、式ｘ（ｉ）＝［ｘｉ ｘｉ＋１ . . . ｘｉ＋ｎ−１］によって定義され、最初のオーバーラップするウィンドウのための前記測定値ｙ（０）は、式ｙ（０）＝Ａ（０）ｘ（０）によって定義される、
に少なくとも部分的によって、センサデータの入力ストリームを、連続するオーバーラップするウィンドウを使用して再帰的にサンプリングする
ように構成される、装置。
【発明の詳細な説明】
【技術分野】
【０００１】
[0001]本発明は、ストリーミングデータの圧縮センシングのための方法およびそれを実行するための手段を対象とする。より詳細には、いくつかの実施形態は、ストリーミングデータ上で圧縮センシングを実行するための再帰的なアルゴリズムを使用するストリーミングデータの圧縮センシングの方法と、ストリーミングデータの圧縮センシングのための方法を実行することができる装置またはシステムまたはコンピュータプログラム製品とを含む。
【背景技術】
【０００２】
[0002]信号処理の分野では、対象の信号は、適切に選択された正規直交基底において、わずかしかない係数を使用することによってスパースとして表され得る。例示的に、フーリエ基底は、画像などの区分的で継続的な信号に関する帯域制限信号またはウェーブレット基底に対して使用される。それぞれの基底の中のわずかな数の係数は、そのような信号を表すために十分であるが、ナイキスト／シャノンのサンプリング定理は、信号帯域幅の少なくとも２倍のサンプリングレートを示唆する。そのようなサンプリングレートは、当技術分野でナイキストレートとして知られている。多くの場合、示されるサンプリングレートは、十分な数の係数よりもずっと大きい。
【０００３】
[0003]最近、信号を、それらの帯域幅に従うのでなく、むしろそれらの情報量、すなわち、信号の自由度の数に従ってサンプリングすることを目指して、圧縮センシング（ＣＳ）の枠組みが発表された。サンプリングに対するこのパラダイムは、いくつかの所与の基底の中でスパースな表現を有する信号に対して、古典的なサンプリング理論と比較してより低いサンプリングレートを示唆する。天文学および生物医学のイメージングに自然に生じる典型的な信号が、このモデルに適する。
【発明の概要】
【０００４】
[0004]本発明は、その実施形態のうちの１つに従って、ストリーミングデータを感知するためのコンピュータ実施方法を提案し、コンピュータ実施方法は、データの入力ストリームを、前記入力データストリームに関する少なくとも１つの以前の測定値を取得するために、オーバーラップするウィンドウ処理を使用して再帰的にサンプリングすることと、後続の測定値を取得するために、前記少なくとも１つの以前の測定値を使用することとを備える。
【０００５】
[0005]本発明の別の実施形態によれば、ストリーミングデータを感知するためのシステムが提案され、システムは複数のモジュールを含み、各モジュールは、データの入力ストリームを、前記入力データストリームに関する少なくとも１つの以前の測定値を取得するために、オーバーラップするウィンドウ処理を使用して再帰的にサンプリングし、後続の測定値を取得するために、前記少なくとも１つの以前の測定値を使用するための、コンピュータ実行可能な命令をその上に有するコンピュータ可読媒体を備える。
【０００６】
[0006]本発明のさらに別の実施形態によれば、ストリーミングデータを感知するための、その上に記録されたコンピュータプログラムを有するコンピュータ可読記憶媒体が提案され、コンピュータプログラムは、データの入力ストリームを、前記入力データストリームに関する少なくとも１つの以前の測定値を取得するために、オーバーラップするウィンドウ処理を使用して再帰的にサンプリングし、後続の測定値を取得するために、前記少なくとも１つの以前の測定値を使用することが可能なアルゴリズムを備える。
【０００７】
[0007]本発明のさらなる実施形態によれば、ストリーミングデータの圧縮センシングを実行するための装置が提案され、装置は、データの入力ストリームを、前記入力データストリームに関する少なくとも１つの以前の測定値を取得するために、オーバーラップするウィンドウ処理を使用して再帰的にサンプリングするために構成された再帰的なサンプラーと、後続の測定値を取得するために、少なくとも１つの以前の測定値を使用するユニットとを備える。
【０００８】
[0008]本発明の一実施形態によれば、ストリーミングデータを感知することは、ストリーミングデータの圧縮センシングであり、ストリーミングデータを感知するための方法は、サンプリングを実行するための再帰的な方式を使用する。後続の測定値を取得するために少なくとも１つの以前の測定値を使用するステップは、再帰的な推定を介した再帰的なサンプリングのステップの間にサンプリングされたデータとしての、入力ストリームを処理することを備える。
【０００９】
[0009]本発明の別の実施形態によれば、本発明によって提案される方法および手段は、以前の推定値取得ステップの間に取得された以前の推定値に関するデータストリームに関する入力情報を伴い、以前の推定値取得ステップは、再帰的なサンプリングステップの前にある。方法は、データストリームの台検出ステップの間に取得される情報に基づいて、回数推定を実行することと、前記再帰的な推定ステップの間に取得されるデータに基づいて、データストリームの台の集合に対して最小２乗推定（ＬＳＥ）値を算出することとを、さらに備える。さらに、方法は、本発明の別の実施形態に従って、平均するステップを備え、平均された値を算出するために算出された最小２乗推定値、回数推定値、および以前の推定値は、平均された値を取得するために平均される。平均された値は、ストリーミングデータに対する新しい推定値を取得するために使用される。
【００１０】
[0010]本発明のさらに別の実施形態によれば、本発明によって提案される方法は、ストリーミングデータの圧縮センシングの計算量を分析し、ストリーミングデータを感知するための方法の誤差の程度を推定するステップを、さらに備える。方法は、新しいウィンドウを復号するために、反復的な最適化アルゴリズムにおいて収束を達成することをさらに備え、達成するステップは、オーバーラップするウィンドウ処理のステップによって使用されるオーバーラップするウィンドウ構造と、以前のウィンドウに関する信号推定値とを活用することを備える。方法は、複数のウィンドウから取得される信号推定値を平均することと、台集合検出を実行することと、信号振幅推定とを、さらに備える。
大きい測定雑音の存在下でのロバストな台推定のための投票方式が、同様に本発明に従って適用され得る。
【００１１】
[0011]本発明のさらなる目的および利点は、それらの含まれる各図面に関連して行われる以下の説明から諒解されよう。
【図面の簡単な説明】
【００１２】
【図１】[0012]本発明の一実施形態によるストリーミングデータを感知するための方法のブロック図。
【図２】[0013]単一の時間ウィンドウにわたる再帰的な圧縮センシング対「単純な手法」に関する平均処理時間を表す図。
【図３】[0014]ＬＡＳＳＯを使用する台集合の推定の結果を表す図。
【図４】[0015]ａ）平均された推定値、ｂ）バイアス除去および平均された推定値、およびｃ）投票および平均化によって取得された推定値に関する誤差プロットを表す図。
【図５】[0016]ストリーミングデータ上の平均されたＬＡＳＳＯ推定値ならびに「投票および平均化」に関する誤差プロットを表す図。
【発明を実施するための形態】
【００１３】
[0017]本発明を実施することの現在熟考される最良の方式の以下の説明は、限定的な意味に理解されるべきでなく、単に本発明の一般的な原理について説明するためになされる。本発明の範囲は、特許請求の範囲に関して決定されるべきである。
【００１４】
[0018]圧縮センシングの分野において多くの進歩がなされてきたが、ストリーミングデータ上で圧縮センシングを実行するための再帰的なアルゴリズムは、依然として取り組まれないままである。連続するウィンドウ処理を通じて入力ストリームに圧縮センシングを適用することによる、雑音のあるサンプルからの信号推定の計算量および安定性は、当技術分野においてまだ取り組まれていない。
【００１５】
[0019]当業者によって理解されるように、本発明の態様は、システム、方法、またはコンピュータプログラム製品として具現化され得る。したがって、本発明の態様は、完全にハードウェアの実施形態、完全にソフトウェアの実施形態（ファームウェア、常駐のソフトウェア、マイクロコードなどを含む）、または、まったく一般に本明細書で「回路」、「モジュール」または「システム」と呼ばれ得る、ソフトウェアおよびハードウェアの態様を組み合わせる実施形態の形態をとり得る。さらに、本発明の態様は、その上に記録されたコンピュータ可読プログラムコードを有する、１つまたは複数のコンピュータ可読媒体（すなわち、データ記憶媒体）で実現されるコンピュータプログラム製品の形態をとり得る。
【００１６】
[0020]１つまたは複数のコンピュータ可読媒体の任意の組合せが、利用され得る。コンピュータ可読媒体は、コンピュータ可読信号媒体またはコンピュータ可読記憶媒体であり得る。コンピュータ可読記憶媒体は、たとえば、それだけには限らないが、電子、磁気、光学、電磁気、赤外線、もしくは半導体のシステム、装置、もしくはデバイス、または前述のものの任意の適当な組合せであり得る。コンピュータ可読記憶媒体のより具体的な例（非網羅的なリスト）は、以下のもの、すなわち、ポータブルコンピュータのディスケット、ハードディスク、ランダムアクセスメモリ（ＲＡＭ）、読出し専用メモリ（ＲＯＭ）、消去可能プログラム可能読出し専用メモリ（ＥＰＲＯＭまたはフラッシュメモリ）、光ファイバ、ポータブルのコンパクトディスク読出し専用メモリ（ＣＤ−ＲＯＭ）、光記憶デバイス、磁気記憶デバイス、または前述のものの任意の適当な組合せを含むはずである。本明細書の文脈では、コンピュータ可読記憶媒体、すなわち、データ記憶媒体は、命令実行システム、装置、またはデバイスによって使用される、またはそれらと組み合わせて使用されるプログラムを含むことができる、または記憶することができる、任意の有形の媒体であり得る。
【００１７】
[0021]コンピュータ可読信号媒体は、コンピュータ可読プログラムコードが組み入れられた伝搬されるデータ信号を、たとえばベースバンド内に、または搬送波の一部として含み得る。そのような伝搬される信号は、それだけには限らないが、電磁気、光学、またはそれらの任意の適当な組合せを含む、様々な形態のうちの任意の形態をとり得る。コンピュータ可読信号媒体は、コンピュータ可読記憶媒体でなく、命令実行システム、装置、またはデバイスによって使用される、またはそれらと組み合わせて使用されるプログラムを、通信、伝搬、または搬送し得る、任意のコンピュータ可読媒体であり得る。
【００１８】
[0022]コンピュータ可読媒体に組み込まれるプログラムコードは、それだけには限らないが、ワイヤレス、ワイヤライン、光ファイバケーブル、ＲＦなど、または前述のものの任意の適当な組合せを含む、任意の適切な媒体を使用して送信され得る。
【００１９】
[0023]本発明の態様の動作を実行するためのコンピュータプログラムコードは、Ｊａｖａ（登録商標）、Ｓｍａｌｌｔａｌｋ、Ｃ＋＋などのオブジェクト指向プログラム言語、および「Ｃ」プログラミング言語または同様のプログラミング言語などの従来の手続き型プログラム言語を含む、１つまたは複数のプログラミング言語の任意の組合せで記述され得る。プログラムコードは、完全にユーザのコンピュータ上で、部分的にユーザのコンピュータ上で、スタンドアロンのソフトウェアパッケージとして、部分的にユーザのコンピュータ上および部分的に遠隔のコンピュータ上で、または完全に遠隔のコンピュータまたはサーバ上で、実行され得る。後者のシナリオでは、遠隔コンピュータは、ローカルエリアネットワーク（ＬＡＮ）またはワイドエリアネットワーク（ＷＡＮ）を含む任意のタイプのネットワークを介してユーザのコンピュータに接続され得、その接続は、（たとえばインターネットサービスプロバイダを使用してインターネットを介して）外部コンピュータに対しても行われてもよい。
【００２０】
[0024]本発明の態様は、本発明の実施形態による、フローチャートの例示ならびに／または方法、装置（システム）およびコンピュータプログラム製品のブロック図を参照して以下に記載される。フローチャートの例示および／またはブロック図の各ブロック、ならびにフローチャートの例示および／またはブロック図でのブロックの組合せは、コンピュータプログラム命令によって実施され得ることが理解されよう。これらのコンピュータプログラム命令は、汎用コンピュータ、専用コンピュータ、またはマシンを形成する他のプログラム可能データ処理装置のプロセッサに提供されてよく、コンピュータまたは他のプログラム可能データ処理装置のプロセッサを介して実行されて、フローチャートおよび／またはブロック図のブロックもしくはブロック群で指定される機能／動作を実装するための手段を生成する。
【００２１】
[0025]これらのコンピュータプログラム命令はまた、特定の方式で機能するように、コンピュータ、他のプログラム可能データ処理装置、または他のデバイスを直接指示し得るコンピュータ可読媒体に記憶され得る。コンピュータプログラム命令はまた、コンピュータまたは他のプログラム可能装置上で実行される命令が、フローチャートおよび／あるいはブロック図のブロックまたはブロック群で指定された機能／動作を実装するためのプロセスを提供するようなコンピュータ実装プロセスを形成するために、コンピュータ、他のプログラム可能装置、または他のデバイス上で一連の動作ステップを実行させるように、コンピュータ、他のプログラム可能データ処理装置、または他のデバイスにロードされ得る。
【００２２】
[0026]以下の説明全体にわたって、大文字でボールド体の文字は行列を表し（たとえば、Ａ）、ボールド体で小文字の文字はベクトルを表す（たとえば、ｘ）。
【００２３】
[0027]以下において、ｘiはベクトルｘの第ｉのエントリを表すために使用され、ａiは行列Ａの第ｉ列を表すために使用される。
【００２４】
[0028]入力ストリームの第ｉのウィンドウのような第ｉのサンプルベクトル、または第ｉのサンプリング行列は、上付き文字によって表される（たとえば、ｘ(i)またはＡ(i)）。
【００２５】
[0029]２つのベクトルａとｂとの間の内積は、
＜ａ，ｂ＞：＝ａTｂ
として表される。
【００２６】
[0030]｜Ｓ｜は集合Ｓの濃度のために示す。
【００２７】
[0031]Ｅx［．］は、条件付き期待値Ｅx［．］＝Ｅ［．｜ｘ］を示す。
【００２８】
[0032]圧縮センシングの分野では、ベクトルまたは行列のいずれかの特徴を述べるために頻繁に使用される用語は、「ｋ−スパース性」、「相互コヒーレンス」、「制限等長性」および「一般ｋ−スパースモデル」である。以下において、本明細書を通して意図されるそれらの意味を示すために、しばらくの間、前記用語が詳しく述べられる。
【００２９】
[0033]ベクトルｘ∈Ｒnに対して、その台はｓｕｐｐ（ｘ）：＝｛ｉ：ｘi≠０｝として定義される。
【００３０】
[0034]同じベクトルｘ∈Ｒnに対して、その擬ノルムｌ0は、‖ｘ‖0：＝｜ｓｕｐｐ（ｘ）｜として定義され、ここで、ｘ0は台の濃度である。
【００３１】
[0035]‖ｘ‖0≦ｋの場合に限って、ベクトルｘはスパースである。
【００３２】
[0036]一般に、ｋ≪ｎであり、ｎは行列Ａの列の数である。
【００３３】
[0037]例示的に、ｘ＝［０  ０  ０  ３  ０−１  ０  ０  ５  ０］の場合、ｘ∈Ｒ10、‖ｘ‖0＝３であり、ｘは３スパースである。
【００３４】
[0038]行列Ａ∈Ｒm×nに関して、相互コヒーレンスは、行列Ａの２つの異なる任意の列の間の、正規化された最大の内積として、次のように定義される。
【００３５】
【数１】
0006495292.tif 000002
【００３６】
[0039]行列Ａ∈Ｒm×nに対して０＜ｋ＜ｎが与えられると、
【００３７】
【数２】
0006495292.tif 000003
【００３８】
のようなδk∈［０，１］が存在する場合、行列Ａは制限等長性（ＲＩＰ）を満たすと言われる。
【００３９】
[0040]この条件は、すべてのｘ∈Ｒnのｋ−スパースなベクトルにとって有効なはずであり、ただし、δkは十分小さい必要がある。
【００４０】
[0041]ガウス行列、ベルヌーイ行列、ＤＦＴ行列からランダムに選択された行などのランダム行列は、それらが高い確率で制限等長性を満たすので、文献では圧縮センシング用の行列として使用されてきたことが知られている。制限等長性を満たす行列の例は、
ａ）ｍ次元の単位球面からサンプリングされたｎ個のランダムベクトル、
ｂ）ｎ次元のフーリエ行列から一様でランダムにｍ行を選択することによって取得されるランダムな部分フーリエ行列、
ｃ）Ａi,j〜Ｎ（０，１／ｍ）を有するランダムなガウス行列、
ｄ）等確率で
【００４１】
【数３】
0006495292.tif 000004
【００４２】
となるランダムなベルヌーイ行列、である。
【００４３】
[0042]最後の２つのケースに関して、行列Ａは、
【００４４】
【数４】
0006495292.tif 000005
【００４５】
以上の確率で、任意のｋ≦ｃ1ｍ／ｌｏｇ（ｎ／ｋ）に対して規定されたδkを満たし、ただし、ｃ1およびｃ2はδkのみに依存する定数である。
【００４６】
[0043]本明細書を通して使用されるさらなる用語が、以下に定義される。
【００４７】
[0044]「再帰的に」は、手順が、自己相似のやり方でものを繰り返すことによって実行されることを示すために使用される。数学およびコンピュータ科学では、その用語は、定義されている関数がそれ自体の定義内で適用される関数を、定義する方法を指す。詳細には、このことは、いくつかのインスタンスに対して他のインスタンスを指し得る有限の表現を使用して、ただし参照のループまたは無限鎖が発生し得ないようなやり方で、無限数のインスタンス（関数値）を定義する。その用語はまた、より一般に、自己相似のやり方で対象を繰り返すプロセスを述べるために使用される。再帰とは、手順のステップのうちの１つが手順それ自体を呼び出すことを伴うとき、その手順が経るプロセスである。再帰を経る手順は、「再帰的」であると言われる。
【００４８】
[0045]信号処理では、ウィンドウ関数（アポダイゼイション関数またはテーパリング関数とも呼ばれる）は、選ばれたいくつかの区間の外側がゼロ値にされる数学関数である。たとえば、区間の内側が定数であり他の場所がゼロである関数は、矩形ウィンドウと呼ばれ、これはその図式表現の形状を述べている。別の関数または波形／データ列がウィンドウ関数によって乗算されると、その積も区間の外側がゼロ値にされ、残されるものはすべてそれらがオーバーラップする部分であり、「ウィンドウを通した見え方」となる。ウィンドウ関数の適用は、スペクトル分析、フィルタ設計、およびビームフォーミングを含む。典型的な適用例では、使用されるウィンドウ関数は非負の滑らかな「ベル形」曲線であるが、矩形、三角形、および他の関数が使用され得る。ウィンドウ関数のより一般的な定義は、それの引数によって乗算されたウィンドウの積が二乗可積分である限り、より詳細には、関数が十分急速にゼロに向かっていく限り、区間の外側が等しくゼロであることをそれらに求めない。変換されるべきデータ集合の長さが所望の周波数分解能をもたらすために必要となる長さよりも長いとき、一般的な操作は、データをより小さい集合へ、またウィンドウ自体を別々に、再分割することである。ウィンドウの縁部における「損失」を低減するために、個々の集合は時間的にオーバーラップしてよい。
【００４９】
[0046]ｘが線形ベクトルｘ∈Ｒnであり、ｙ∈Ｒmが、Ａ∈Ｒm×nをサンプリング（センシング）行列として取得されたサンプルのベクトル
【００５０】
【数５】
0006495292.tif 000006
【００５１】
である場合、本発明はｍ≪ｎのときにｘを復元するための方法および手段を提案する。式（１）を用いて表されるシステムは、劣決定の線形システムである。圧縮センシングによれば、主な成果は、ｘがｋ−スパースでｋ＜ｃm／ｌｏｇ（ｎ／ｋ）となる場合、この未定の線形システムの解があり得ることである。
【００５２】
[0047]測定値ｙに至る最もスパースなベクトルｘを見つけるために、以下に述べる問題Ｐ0が解かれるべきである。この問題は、非決定性多項式時間困難、すなわち、ＮＰ困難であり、Ａの列のすべての部分集合にわたる探索を必要とする。当技術分野から知られているように、Ｈに対して多項式時間チューリング還元可能であるＮＰ完全な問題Ｌが存在する（すなわち、Ｌ≦TＨ）場合に限って、問題ＨはＮＰ困難である。言い換えれば、Ｌは、Ｈにとっての神託を有する神託機械によって、多項式時間において解かれ得る。
【００５３】
[0048]問題Ｐ0は、
【００５４】
【数６】
0006495292.tif 000007
【００５５】
として提示される。
【００５６】
[0049]問題Ｐ0が一般にＮＰ困難であるので、この問題は扱いやすい方法によって「近似」されなければならない。線形の測定値からスパースなベクトルを復元するために、２つの凸最適化問題が使用される。
【００５７】
[0050]第１の最適化問題は「基底追跡」と呼ばれ、問題Ｐ0を解くことはｌ1最小化問題ＢＰ、
【００５８】
【数７】
0006495292.tif 000008
【００５９】
をすべてのｋ−スパースなベクトルｘについて解くことと同等であり、Ａが
【００６０】
【数８】
0006495292.tif 000009
【００６１】
に関して制限等長性（ＲＩＰ）を満たす場合、上述の問題はＰ0と同等である。最適化問題（ＢＰ）は基底追跡と呼ばれる。（ＢＰ）は線形プログラムとして書き直され得るので、（ＢＰ）を解くことは、大きいインスタンスに対して概して扱いにくい（Ｐ0）を解くことと比べて、たとえば、内点法を介すると計算量的に効率がよい。
【００６２】
[0051]第２の最適化問題は、最小絶対選択収縮演算子（ＬＡＳＳＯ）と呼ばれる。雑音の存在下で、測定モデルｙ＝Ａｘは、
【００６３】
【数９】
0006495292.tif 000010
【００６４】
となり、ここで、ｗ∈Ｒmは加法的測定雑音を表す。
【００６５】
[0052]この設定では、基底追跡の変形、すなわち、統計学の文献においてＬＡＳＳＯとして最もよく知られている、
【００６６】
【数１０】
0006495292.tif 000011
【００６７】
のような基底追跡雑音除去（ＢＰＤＮ）が適用されてよく、ただし、
【００６８】
【数１１】
0006495292.tif 000012
【００６９】
は測定値の中に加法的雑音の割合を占めるように適切に選ばれる。
【００７０】
[0053]当技術分野で知られているように、双対性によって、問題は非制約形最適化問題、すなわち、
【００７１】
【数１２】
0006495292.tif 000013
【００７２】
として同等に与えられ得、ここで、λは、スパース性と再構成誤差との間のトレードオフを制御する正則化パラメータである。
【００７３】
[0054]ストリーミングデータ上で圧縮センシングを実行するための再帰的な方式を編み出す際に有用な定理は、Ａが
【００７４】
【数１３】
0006495292.tif 000014
【００７５】
に関して制限等長性（ＲＩＰ）を満たす場合に、式（３）の解ｘ*が公式
【００７６】
【数１４】
0006495292.tif 000015
【００７７】
に従うことを提示する、ＬＡＳＳＯの誤差に関する定理であり、ここで、
【００７８】
【数１５】
0006495292.tif 000016
【００７９】
はモデルの不整合を示し、
【００８０】
【数１６】
0006495292.tif 000017
【００８１】
は雑音を示す。Ｃ0およびＣ1は定数であり、ここで、ｘkは大きい方のｋ個の成分以外は０に設定されたベクトルｘである。言い換えれば、ｘkは、最大の大きさを有するｘのｋ個の多くの要素を維持することによって取得されるベクトルである。
【００８２】
[0055]特に、ｘがｋ−スパースであり
【００８３】
【数１７】
0006495292.tif 000018
【００８４】
の場合、
【００８５】
【数１８】
0006495292.tif 000019
【００８６】
である。
【００８７】
[0056]その定理は、再構成誤差が２つの項の和によって上界を有し、その１番目はモデルの不整合による誤差であり、２番目は測定雑音分散に比例することを提示する。
【００８８】
[0057]かぎとなるのは、Ｃを各インスタンスに依存する定数として、
【００８９】
【数１９】
0006495292.tif 000020
【００９０】
の場合、等長定数における仮定が、単位球面からサンプリングされたランダムなベクトル、ランダムなガウス行列およびランダムなベルヌーイ行列から取得される行列によって高い確率で満たされることである。
【００９１】
[0058]当技術分野において、ＬＡＳＳＯの誤差が、ほぼ理想的な台検出のために使用され得ることが示された。ほぼ理想的な台検出について特徴的な成果を提示するために、一般ｋ−スパースモデルが定義される。
【００９２】
[0059]ｘ∈Ｒnがｋ−スパースな信号を表し、Ｉｘ：＝ｓｕｐｐ（ｘ）がそれの台集合である場合、
１）ｘの台Ｉx⊂｛１，２，．．．，ｎ｝が一様でランダムに選択され、｜Ｉx｜＝ｋであり、
２）非ゼロの符号が等しく−１および１でありそうなことがＩｘに条件付けられる場合、信号ｘは、一般ｋ−スパースモデルによって生成されると言われる。
【００９３】
[0060]ｋ−スパースな信号の台集合は、次のように検出され得る。
【００９４】
[0061]定数ｃ１＞０についてμ（Ａ）≦ｃ1／ｌｏｇｎと仮定すれば、ｘは一般ｋ−スパースモデルから生成され、定数ｃ２に関して、
【００９５】
【数２０】
0006495292.tif 000021
【００９６】
である。
【００９７】
[0062]Ｉｘ：＝ｓｕｐｐ（ｘ）に関して、
【００９８】
【数２１】
0006495292.tif 000022
【００９９】
となる場合、
ｗ〜Ｎ（０，σ2Ｉ）
の場合の測定に関して
【０１００】
【数２２】
0006495292.tif 000023
【０１０１】
を選ぶことによって取得されるＬＡＳＳＯ推定値は、
少なくとも
【０１０２】
【数２３】
0006495292.tif 000024
【０１０３】
の確率で、
【０１０４】
【数２４】
0006495292.tif 000025
【０１０５】
【数２５】
0006495292.tif 000026
【０１０６】
に従う。
【０１０７】
[0063]要素
Ａi,j〜Ｎ（０，１／ｍ）
を有するサンプリング行列に関して、作用素ノルムは
【０１０８】
【数２６】
0006495292.tif 000027
【０１０９】
であり、したがって、定理におけるスパース性の条件は、ｋ≦ｃ1ｍ／ｌｏｇｎとなる。
【０１１０】
[0064]この不等式が満たされるために、ｍとしての値は
【０１１１】
【数２７】
0006495292.tif 000028
【０１１２】
となる必要がある。
【０１１３】
[0065]さらに、ランダムなガウス行列
【０１１４】
【数２８】
0006495292.tif 000029
【０１１５】
に関して、コヒーレンスにおける条件はｍ＞Ｏ（ｌｏｇ3ｎ）の場合に満たされる。
【０１１６】
[0066]境界を組み合わせると、ｍが
ｍ≧ｍｉｎ｛Ｏ（ｋｌｏｇｎ），Ｏ（ｌｏｇ3ｎ）｝
であることが必要である。
【０１１７】
[0067]直交マッチング追跡（ＯＭＰ）は、スパースなベクトルｘを雑音のない測定値ｙ＝Ａｘから復元することを目指すグリーディーアルゴリズムである。アルゴリズムは、すでに選択された列の線形スパンに投影することによってｙを近似することの、残余誤差を最小限にする列を反復的に選択することによって、Ａの列の部分集合を出力する。測定行列Ａの相互コヒーレンスが
【０１１８】
【数２９】
0006495292.tif 000030
【０１１９】
を満たす場合、ＯＭＰがｋ−スパースな信号を雑音のない測定値から復元することが示される。
【０１２０】
[0068]ＬＡＳＳＯのために編み出され、滑らかでない凸最適化のための近接アルゴリズムによってもたらされたアルゴリズムが存在する。すなわち、ＩＳＴＡは近接勾配法であり、ＦＩＳＴＡは加速された近接勾配法であり、ＳＡＬＳＡは代替の方向乗数法の適用である。
【０１２１】
[0069]Ｇ（ｘ）が式（４）におけるＬＡＳＳＯの目的関数でありｘ*＝ａｒｇ  ｍｉｎＧ（ｘ）の場合にＧ（ｘt）−Ｇ（ｘ*）として定義される誤差に関して、誤差は、ＩＳＴＡに対して１／ｔ、ＦＩＳＴＡに対して１／ｔ2、ＳＡＬＳＡに対して１／ｔ2につれて減衰し、ここで、ｔは反復の数である。当技術分野では、また、滑らかでない凸最適化のためのニュートン型の方法が知られており、その場合、収束速度は１＝ｔ2ほど悪くないが、局所的に２次となる。
【０１２２】
[0070]対象の信号は、ストリーミングデータを処理するときと同様に無限数列、｛ｘi｝i=0,1,...である。そのような対象の信号に関して、ストリーミング信号から取り出される第ｉのウィンドウは、
【０１２３】
【数３０】
0006495292.tif 000031
【０１２４】
として定義される。
【０１２５】
[0071]ｘ(i)がスパースであると知られている場合、上記に概説された手段が、各ウィンドウの中の信号部分、したがって、データストリームを復元するために適用可能である。しかしながら、必要とされる演算はコストがかかり、効率のよいオンライン実装は不確かである。
【０１２６】
[0072]したがって、本発明によれば、ストリーミングデータを効率よくサンプリングし復元するための方法が提案される。そのような方法は、再帰的な圧縮センシング方法であり、以下で詳細に説明される。本明細書でさらに詳細に示されるように、本発明の方法は、サンプリングと推定の両方の部分において低複雑度を示し、そのアルゴリズムを効率のよいオンライン実装にとって適当なものにする。
【０１２７】
[0073]無限数列｛ｘi｝i=0,1,...が｛ｘi｝を用いて示され、長さｎの第ｉのウィンドウがｘ(i)∈Ｒnを用いて示される。
【０１２８】
[0074]Ｒにおいて入力を有する動的モデルが
【０１２９】
【数３１】
0006495292.tif 000032
【０１３０】
として表される。
【０１３１】
[0075]本発明の方法により、推定値
【０１３２】
【数３２】
0006495292.tif 000033
【０１３３】
を形式
【０１３４】
【数３３】
0006495292.tif 000034
【０１３５】
としての連続する測定値ｙ(i)を使用して提供する、ロバストで低複雑度のスライディングウィンドウアルゴリズムの設計が可能になり、ここで、｛Ａ(i)｝は測定行列のシーケンスである。｛ｘi｝が各ウィンドウの中で十分にスパースな場合、すなわち、ｋ≪ｎとして各ｉについて‖ｘ(i)‖0≦ｋである場合、または、この条件が十分に高い確率で遵守される場合、ロバストで低複雑度のスライディングウィンドウアルゴリズムの設計が可能である。
【０１３６】
[0076]Ａ(i)が
【０１３７】
【数３４】
0006495292.tif 000035
【０１３８】
に関して制限等長性を満たす場合、本明細書において前に検討された方法は、漸進的に推定値｛ｘ(i)｝に適用され得る。そのようなアルゴリズムをオンラインで実行することはコストがかかり、したがって、せいぜいアドホックとしてみなされ得るような方法の代替物を設計することが望ましい。
【０１３９】
[0077]本発明によれば、連続するウィンドウの間の信号オーバーラップが活用され、次のように再帰的なサンプリング（符号化ステップ）と再帰的な推定（復号ステップ）とからなる。
【０１４０】
[0078]再帰的なサンプリングのステップに関して、各ｙ（ｉ）に関する行列乗算を避けるために、Ａ（ｉ）は、最小の計算オーバーヘッドでｙ（ｉ＋１）を計算する際にｙ（ｉ）が再使用され得るように設計され、すなわち、
【０１４１】
【数３５】
0006495292.tif 000036
【０１４２】
となる。
【０１４３】
[0079]再帰的な推定のステップに関して、反復的な最適化方式の収束を高速化するために、以前のウィンドウ
【０１４４】
【数３６】
0006495292.tif 000037
【０１４５】
に対応する推定値が、
【０１４６】
【数３７】
0006495292.tif 000038
【０１４７】
としての推定手順の開始点
【０１４８】
【数３８】
0006495292.tif 000039
【０１４９】
を導くために使用され、すなわち、
【０１５０】
【数３９】
0006495292.tif 000040
【０１５１】
となる。
【０１５２】
[0080]以下において、再帰的なサンプリングと再帰的な推定の両方のステップが、より詳細に説明される。
【０１５３】
[0081]再帰的なサンプリングのステップに関して、最小の計算オーバーヘッドを特色にする再帰的なサンプリング方式が提案される。最初の反復ｔ＝０において事前の推定値は存在せず、したがって、計算されるものは
【０１５４】
【数４０】
0006495292.tif 000041
【０１５５】
である。
【０１５６】
[0082]センシング行列Ａ(i)のシーケンスは、
【０１５７】
【数４１】
0006495292.tif 000042
【０１５８】
として再帰的に選ばれ、ここで、
【０１５９】
【数４２】
0006495292.tif 000043
【０１６０】
はＡ(i)の第ｌ列であり、Ｐは置換行列
【０１６１】
【数４３】
0006495292.tif 000044
【０１６２】
である。
【０１６３】
[0083]以下の補助定理は、この符号化方式の成功を保証する。すなわち、Ａ(0)が所与のｋに対する定数δkに関して制限等長性を満たす場合、上式（８）において定義されたようなＡ(i)は、同じｋ、およびδkに関して、同様に制限等長性を満たす。
【０１６４】
[0084]Ａ(i)＝Ａ(0)Ｐiであることは式（８）から結果として生じ、Ａ(i)はＡ(0)の列を並べ替えることによって取得される。定義により、制限等長性は‖ｘ‖0のみに依存し、ｘのエントリの置換、すなわち、Ａ(0)の列の置換に影響を受けない。
【０１６５】
[0085]Ａ(i)の特定の再帰的な選択が与えられると、ｙ(i+1)は、
【０１６６】
【数４４】
0006495292.tif 000045
【０１６７】
として計算される。
【０１６８】
[0086]対象の信号が雑音を備えるとき、雑音のある測定値は、
【０１６９】
【数４５】
0006495292.tif 000046
【０１７０】
として言及される。
【０１７１】
[0087]したがって、
【０１７２】
【数４６】
0006495292.tif 000047
【０１７３】
となる。
【０１７４】
[0088]この式のｂ(i+1)の値の代わりにｙ(i+1)を用いることによって、得られるものは、
【０１７５】
【数４７】
0006495292.tif 000048
【０１７６】
である。
【０１７７】
[0089]ｚ(i)：＝ｗ(i)−ｗ(i-1)を定義することによって、｛ｗ(i)｝が独立増分プロセスの場合、ｚ(i)およびｚ(i+1)は独立している。
【０１７８】
[0090]式（８）で与えられるサンプリング行列｛Ａ(i)｝i=0,1,...の特定の選択は、条件
【０１７９】
【数４８】
0006495292.tif 000049
【０１８０】
を満たす。
【０１８１】
[0091]ｖ(i)：＝Ｐ(i)ｘ(i)としてｖ(i)を定義することによって、再帰的なサンプリングは、同じ測定行列Ａ(0)を使用することによってｖ(i)を符号化することとして見られ得る。式（６）で与えられるｘ(i)の特定の構造を用いて、ｖ(i)およびｖ(i-1)のエントリのすべては、
【０１８２】
【数４９】
0006495292.tif 000050
【０１８３】
を除いて等しい。
【０１８４】
[0092]対象の信号の再帰的な推定に関して、
【０１８５】
【数５０】
0006495292.tif 000051
【０１８６】
に対する推定値は、推定値
【０１８７】
【数５１】
0006495292.tif 000052
【０１８８】
を活用することによって見つけられる。
【０１８９】
[0093]反復的アルゴリズムでは、収束速度は、開始点の最適解までの距離に依存する。加速された収束を達成するために、ウィンドウ間のオーバーラップが活用され、以下の開始点が使用され、すなわち、
【０１９０】
【数５２】
0006495292.tif 000053
【０１９１】
となり、ただし、ｊ＝２，．．．，ｎ−１に対して
【０１９２】
【数５３】
0006495292.tif 000054
【０１９３】
は以前のウィンドウに基づく最適解の部分である。このことは、最適化の文献では「ウォームスタート」と呼ばれる。開始点をそのように選ぶことによって、収束を得るために予期される反復の数が低減される。このことは、本明細書の後の部分で実際に立証され、そこで、定量的な結果が詳細に説明される。
【０１９４】
[0094]以下において、対象のスパース信号は、それらが所与の正規直交基底にあるものとして説明される。
【０１９５】
[0095]本明細書ではここまで、所与のｎ∈Ｚ+に対して、シーケンス｛ｘi｝から取得される長さｎのウィンドウｘ(i)がスパース性の制約‖ｘ(i)‖0≦ｋ、∀ｉを満たすことが、暗黙のうちに仮定されていた。一般に、ｘ(i)は、それ自体スパースでないが、適切に選択された基底においてスパースとして表され得ることがあるかも知れない。
【０１９６】
[0096]α(i)をスパースとして、ｘ(i)∈Ｒnは、所与の正規直交基底Φにおいてｘ(i)＝Φα(i)のときにスパースとして表せるものである。
【０１９７】
[0097]サイズｎのウィンドウにわたるシーケンス｛ｘi｝全体に対して共通の基底を仮定すると、得られるものは、
【０１９８】
【数５４】
0006495292.tif 000055
【０１９９】
である。
【０２００】
[0098]引き継がせるべき圧縮センシング推定に対して、Ａ(i)Φは制限等長性を満たす必要がある。制限等長性は、ランダム行列Ａ(i)と任意の固定行列との積に関して高い確率で満たされる。このケースでは、信号をスパース性基底において復元するためのＬＡＳＳＯ問題、α(i)は、
【０２０１】
【数５５】
0006495292.tif 000056
【０２０２】
として表現され、ここで、入力信号はｘ(i)＝Φα(i)によって与えられる。
【０２０３】
[0099]解かれるべき必要がある問題は、Ｅ［α(i+1)｜α(i)］のような再帰的な推定において、加速された収束を得るための良好な初期推定値を有するように、α(i+1)に対してα(i)に基づく再帰的な更新をどのように見つけるかということである。
【０２０４】
[00100]式（６）を使用すると、得られるものは
【０２０５】
【数５６】
0006495292.tif 000057
【０２０６】
であり、ここで、０n-1はすべての要素が０に設定された長さｎ−１のベクトルである。
【０２０７】
[00101]ｘ(i)＝Φα(i)なので、
【０２０８】
【数５７】
0006495292.tif 000058
【０２０９】
【数５８】
0006495292.tif 000059
【０２１０】
が得られる。
【０２１１】
[00102]前の式においてΨ＝Φ-1を両側に左から掛けると、それは、
【０２１２】
【数５９】
0006495292.tif 000060
【０２１３】
に従い、ここで、Π：＝ＰTは式（９）で与えられた置換行列であり、
[00103]
【０２１４】
【数６０】
0006495292.tif 000061
【０２１５】
および
【０２１６】
【数６１】
0006495292.tif 000062
【０２１７】
は、それぞれ、正規直交基底Φの最初の行および最後の行である。
【０２１８】
[00104]フーリエ基底は、効率のよい更新規則がそのような基底に関して導かれ得るので、Φについて特に興味深い。フーリエ基底に対する再帰的なサンプリングは、次のようになる。
【０２１９】
[00105]Φが、エントリ
【０２２０】
【数６２】
0006495292.tif 000063
【０２２１】
を有するｎ×ｎの逆離散フーリエ変換（ＩＤＦＴ）行列であり、
【０２２２】
【数６３】
0006495292.tif 000064
【０２２３】
の場合、そのようなケースでは、
【０２２４】
【数６４】
0006495292.tif 000065
【０２２５】
となり、ここで、Ωnは、（Ωn）i,i＝ω-(i-1)を有するｎ×ｎの対角行列であり、Ψ＝Φ-1は正規直交フーリエ基底である。
【０２２６】
[00106]この特定のケースでは、ΨΠ＝ΩnΨおよびΨΦ＝Ｉのように、時間領域における循環シフトはフーリエ領域における複素指数関数による乗算に相当するので、式（１１）は式（１２）へと簡単になる。
【０２２７】
[00107]上記から、α(i)に基づいてα(i+1)を算出するための計算の数は一般にＯ（ｎ2）であるが、フーリエ基底に関しては、α(i)を乗算する行列が対角なのでＯ（ｎ）であることが理解され得る。
【０２２８】
[00108]前に示したように、雑音の存在下で、Ｅ［α(i+1)｜α(i)］としての推定値は、加速された収束を達成するために、反復ＬＡＳＳＯソルバーにおけるウォームスタートのための開始点として使用される。
【０２２９】
[00109]誤差分散を改善するための１つのやり方は、連続するウィンドウから取得された推定値を平均することによる。推定値
【０２３０】
【数６５】
0006495292.tif 000066
【０２３１】
を使用すると、平均推定値
【０２３２】
【数６６】
0006495292.tif 000067
【０２３３】
は、ストリーミング信号の第ｉのエントリ、すなわち、ｘiに対して、
【０２３４】
【数６７】
0006495292.tif 000068
【０２３５】
として定義され、ここで、ｉ≧ｎ−１に対するｎ個の多くの推定値と、ｉ＜ｎ−１に対するｉ＋１個の多くの推定値とを平均する。
【０２３６】
[00110]表記上の簡単のためにｉ≧ｎ−１を考察すると、さらに得られるものは
【０２３７】
【数６８】
0006495292.tif 000069
【０２３８】
であり、ここで、（ａ）は、ｘ2に適用されるイェンセンの不等式から結果として生じる。不等式は、再構成誤差が、推定値を平均することのみによって小さくされ得ることを暗示する。
【０２３９】
[00111]以下において、再構成誤差
【０２４０】
【数６９】
0006495292.tif 000070
【０２４１】
の予期されるｌ2−ノルムは、式を拡張すること、および、
【０２４２】
【数７０】
0006495292.tif 000071
【０２４３】
を使用することによって、分析される。
【０２４４】
[00112]表記上の便利のため、ｉ≧ｎ−１のケースが考察され、ｉ＜ｎ−１のケースは類似である。
【０２４５】
【数７１】
0006495292.tif 000072
【０２４６】
[00113]得られた等式は、推定量のいわゆるバイアス分散の分解である。ウィンドウの長さが増大するにつれて、第２項はゼロに近づき、再構成誤差はＬＡＳＳＯのバイアスの二乗に漸近的に収束することが理解される。
【０２４７】
[00114]以下において、本発明に従って提案されるアルゴリズムが説明される。
【０２４８】
[00115]一般に、最小絶対選択収縮演算子（ＬＡＳＳＯ）は、ｍ≦ｎとしてＲm→Ｒnの写像を行うとき、バイアスのある推定量を生じる。ウィンドウ間のオーバーラップがＬＡＳＳＯ推定値を直接平均することによって利用される場合、再構成誤差は、バイアスに起因してゼロへ進まない。一方、最小２乗推定（ＬＳＥ）は、優決定のシステムに関するバイアスのない推定量であり、本明細書で上記に示したように、ＬＡＳＳＯは、ＬＳＥがその後適用され得る信号の台集合を推定するために使用され得る。これらの観測に基づいて、サンプリングされた信号を推定誤差を低減するように復元するために、２段階の推定手順が提案される。最初に、ＬＡＳＳＯ推定値
【０２４９】
【数７２】
0006495292.tif 000073
【０２５０】
が取得され、次いで、それがバイアス除去アルゴリズムへの入力として使用される。バイアス除去に関して、
【０２５１】
【数７３】
0006495292.tif 000074
【０２５２】
を得るためにＬＳＥがＬＡＳＳＯ推定値の台集合で実行され、‖ｘ(i)‖0≦ｍであり台が正しく識別されるとき、それは信号の真の非ゼロのバイアスのない推定量を与える。その後、連続するウィンドウにわたって取得されバイアス除去された推定値が、平均される。アルゴリズムのための方法のブロック図および擬似コードが、それぞれ、以下に付加される図およびアルゴリズム１に見られ得る。
【０２５３】
[00116]アルゴリズム１  再帰的な圧縮センシング：
入力：Ａ(0)∈Ｒm×n、｛ｘ｝、λ≧０
出力：推定値
【０２５４】
【数７４】
0006495292.tif 000075
【０２５５】
１．台選択回数：｛ｖ｝←｛０｝、信号推定値：
【０２５６】
【数７５】
0006495292.tif 000076
【０２５７】
２．
【０２５８】
【数７６】
0006495292.tif 000077
【０２５９】
３．
【０２６０】
【数７７】
0006495292.tif 000078
【０２６１】
４．
【０２６２】
【数７８】
0006495292.tif 000079
【０２６３】
５．
【０２６４】
【数７９】
0006495292.tif 000080
【０２６５】
６．
【０２６６】
【数８０】
0006495292.tif 000081
【０２６７】
７．
【０２６８】
【数８１】
0006495292.tif 000082
【０２６９】
８．
【０２７０】
【数８２】
0006495292.tif 000083
【０２７１】
９．
【０２７２】
【数８３】
0006495292.tif 000084
【０２７３】
１０．
【０２７４】
【数８４】
0006495292.tif 000085
【０２７５】
１１．終了。
【０２７６】
[00117]本発明の一実施形態によるストリーミングデータを感知するための方法のブロック図が、図１に表される。本実施形態による方法は、データの入力ストリームを、少なくとも以前の測定値を取得するために、オーバーラップするウィンドウ処理のステップを使用して再帰的にサンプリングし、後続の測定値を取得するために、前記以前の測定値を使用するステップとを備える。より正確には、方法は、データの入力ストリームの再帰的なサンプリングのステップ１０２を備える。再帰的なサンプリングのステップ１０２の間にサンプリングされたデータは、再帰的な推定ステップ１０４を介して処理される。再帰的なサンプリングの前の、以前の推定値取得ステップ１１６の間に取得された以前の推定値に関する情報は、同様に、再帰的な推定のステップ１０４の間に帰属させられる。再帰的なサンプリングアルゴリズムのステップ６に関して上述したように、再帰的な推定のステップ１０４の間に取得されたデータは、台検出のステップ１０６の間に利用される。台検出ステップの結果として処理された情報は、図１のステップ１１０に図示し再帰的なサンプリングアルゴリズムのステップ７に対応するように、回数推定のために使用され得る。再帰的なサンプリングアルゴリズムのステップ８に関して上述したように、ステップ１０６において取得された情報は、台集合においてＬＳＥを算出するステップ１０８の間に利用される。再帰的なサンプリングアルゴリズムのステップ９に関して上述したように、その後、台集合におけるＬＳＥ、および推定回数は、ステップ１１２において平均される。方法の一実施形態によれば、ステップ１１６の間に取得された以前の推定値は、同様に、ステップ１１２において平均される。再帰的なサンプリングアルゴリズムのステップ１０に関して上述したように、新しい推定値がステップ１１４において取得される。
【０２７７】
[00118]そのような１つの実施形態による方法は、同様に、方法の計算量と推定誤差とを分析することができる。
【０２７８】
[00119]より正確には、以下において、方法の複雑度および誤差分散が分析され、よりロバストな台検出のための投票アルゴリズムが導入される。
【０２７９】
[00120]方法の一実施形態を表す図１のブロック図は、連続するウィンドウ間に可変のオーバーラップを備える方法に拡張され得る。
【０２８０】
[00121]考察中に取り上げられることは、感知することが０＜τ≦ｎのオーバーラップを用いた循環するウィンドウ処理を介して実行されることの一般化である。
【０２８１】
[00122]Ａ∈Ｒm×nがサンプリング行列を表す場合、ｉはウィンドウインデックスを表し、ηiはサンプリング効率であり、それは時間（ｎ＋ｉ）までに取得される総サンプルの、感知されるエントリの数に対する比である。１つのウィンドウに関して、サンプリング行列がＡ∈Ｒm×nなのでサンプリング効率はｍ／ｎである。
【０２８２】
[00123]第ｉのウィンドウの端部までに、ｉｍ個のサンプルを取得しながらｎ＋（ｉ−１）τ個の要素が復元されている。漸近のサンプリング効率は
【０２８３】
【数８５】
0006495292.tif 000086
【０２８４】
である。
【０２８５】
[00124]代わりに、ｅｎ符号化において使用される符号化がランクτの更新を使用する場合、すなわち、サンプリング行列をτ回循環シフトすることによって得られる行列を使用することによる場合、漸近のサンプリング効率は、
【０２８６】
【数８６】
0006495292.tif 000087
【０２８７】
となる。
【０２８８】
[00125]後者のケースでは、再帰的なサンプリング手法は、各時間インスタンスについて１つのサンプルを取得することと漸近的に同等である。そのような手法の利点は、雑音抑圧にある。オーバーラップしたウィンドウを採用することによって、各要素は最小
【０２８９】
【数８７】
0006495292.tif 000088
【０２９０】
回の多くの回数において感知され、したがって、複数を使用する協調復号が、推定精度を向上させるために使用され得る。
【０２９１】
[00126]信号の台推定へのＬＡＳＳＯの適用が、本明細書において前に説明された。本明細書ではさらに、大きい測定雑音におけるよりロバストな台検出のために、連続するウィンドウにわたって推定される台を利用する方法が導入される。信号の大きさが雑音レベルを越えるほど十分大きくないとき、上述の台検出メカニズムは、非ゼロの位置を逃すことがあり（フォールスネガティブ）、または誤りの台を検出することがある（フォールスポジティブ）。したがって、本明細書において前に説明した台検出定理は、成功確率を低減するという犠牲を伴って、より小さい最小の非ゼロ値に対して台を検出するために、より小さい正則化定数、λを使用することができる。フォールスポジティブが、すべてのｉについて集合｛０，．．．，ｎ−１｝＼ｓｕｐｐ（ｘ(i)）の上でランダムに分布すると仮定すると、位置が台として検出されるために必要となる最小の回数にしきい値を導入することによって、低い信号対雑音領域においてフォールスポジティブを低減することができる。
【０２９２】
[00127]「投票機」を導入することによって、投票することを用いて得られる２段階アルゴリズムが、図１における台検出ブロック１０６内に表され得る。２段階アルゴリズムは、
【０２９３】
【数８８】
0006495292.tif 000089
【０２９４】
のようなＬＡＳＳＯを解くことによって作用する。
【０２９５】
[00128]ξ1が＞０として設定される場合、
【０２９６】
【数８９】
0006495292.tif 000090
【０２９７】
の絶対値がξ1よりも大きいインデックスが、ｘ(i)の台を推定するために見つけられ、第ｉのウィンドウにおいて
【０２９８】
【数９０】
0006495292.tif 000091
【０２９９】
となる。
投票を含むシーケンスは｛ｖi｝として、インデックスｉが最小２乗推定（ＬＳＥ）において使用される回数は｛Ｌl｝として、定義される。アルゴリズムの初めに、｛ｖi｝および｛Ｌl｝はゼロに設定される。各ウィンドウに対して、集合の中にある位置についての投票が加えられ、集合は、
【０３００】
【数９１】
0006495292.tif 000092
【０３０１】
によって示され、ここで、下付き文字
【０３０２】
【数９２】
0006495292.tif 000093
【０３０３】
は、ウィンドウ内のインデックスをストリーミングデータ上の大域的なインデックスに変換するために使用される。投票｛ｖi｝の回数にしきい値ξ2∈Ｚ+を適用することによって、非ゼロとして認められるべきものとして十分多くの回数投票されたインデックスが見つけられ、それらは
【０３０４】
【数９３】
0006495292.tif 000094
【０３０５】
に記憶される。
【０３０６】
[00129]しきい値ξ2は、
【０３０７】
【数９４】
0006495292.tif 000095
【０３０８】
のように選ばれ、したがって、ＬＳＥに対して優決定のシステムをもたらす。優決定の最小２乗問題は、これらのインデックス
【０３０９】
【数９５】
0006495292.tif 000096
【０３１０】
[00130]に基づいて解かれ、ここで、
【０３１１】
【数９６】
0006495292.tif 000097
【０３１２】
は集合
【０３１３】
【数９７】
0006495292.tif 000098
【０３１４】
によってインデックスが付けられたＡ(i)の列を抽出することによって得られる行列である。次いで、最小２乗推定値の平均を実行するために、ＬＳＥ手順において使用されるエントリに関して、復元の数が
【０３１５】
【数９８】
0006495292.tif 000099
【０３１６】
のようにインクリメントされる。
【０３１７】
[00131]ベクトル
【０３１８】
【数９９】
0006495292.tif 000100
【０３１９】
は、
【０３２０】
【数１００】
0006495292.tif 000101
【０３２１】
の中にあり、ベクトルｘ’∈Ｒnは、
【０３２２】
【数１０１】
0006495292.tif 000102
【０３２３】
によってインデックスが付けられた要素を
【０３２４】
【数１０２】
0006495292.tif 000103
【０３２５】
としての最小２乗推定値に設定し、他のすべてインデックスを０に設定することによって生成される。次いで、平均推定値が、
【０３２６】
【数１０３】
0006495292.tif 000104
【０３２７】
のように更新される。
【０３２８】
[00132]一実施形態による方法の推定誤差分散および計算量が、以下において分析される。
【０３２９】
[00133]２段階ＲＣＳ法の推定誤差分散の分析が行われる前に、以下の補助定理が導入される。
【０３３０】
[00134]補助定理５．１：式（４）におけるＬＡＳＳＯの解を
【０３３１】
【数１０４】
0006495292.tif 000105
【０３３２】
によって表し、その台集合を
【０３３３】
【数１０５】
0006495292.tif 000106
【０３３４】
によって表し、列ＡIに制限される最小２乗解を
【０３３５】
【数１０６】
0006495292.tif 000107
【０３３６】
によって表すと、
次式が満たされる。
【０３３７】
【数１０７】
0006495292.tif 000108
【０３３８】
[00135]選択される台とは無関係に、以下は、ＬＡＳＳＯ推定、およびＬＡＳＳＯ推定値の台に適用される最小２乗に関して有効である。
【０３３９】
【数１０８】
0006495292.tif 000109
【０３４０】
【数１０９】
0006495292.tif 000110
【０３４１】
ただし、
【０３４２】
【数１１０】
0006495292.tif 000111
【０３４３】
である。ＬＡＳＳＯの最適性条件は、
【０３４４】
【数１１１】
0006495292.tif 000112
【０３４５】
[00136]をもたらし、ここで、ｓｇｎ（ｖ）はベクトルに拡張された符号関数である。正規方程式は、
【０３４６】
【数１１２】
0006495292.tif 000113
【０３４７】
を示す。
【０３４８】
[00137]したがって、
【０３４９】
【数１１３】
0006495292.tif 000114
【０３５０】
であり、ここで、（ａ）は式（１５）および正規方程式から結果として生じ、（ｂ）は
【０３５１】
【数１１４】
0006495292.tif 000115
【０３５２】
【数１１５】
0006495292.tif 000116
【０３５３】
から結果として生じ、（ｃ）は
【０３５４】
【数１１６】
0006495292.tif 000117
【０３５５】
から結果として生じる。
【０３５６】
[00138]雑音が台検出にかかわらず無相関であると仮定される場合、すなわち、ｉ≠ｊについて
【０３５７】
【数１１７】
0006495292.tif 000118
【０３５８】
であり、Ａｉが、第ｉのウィンドウの中で台検出が成功したという事象を表す場合、
【０３５９】
【数１１８】
0006495292.tif 000119
【０３６０】
となる。
【０３６１】
[00139]以下の定理は、提案される２段階アルゴリズムの再構成誤差分散における上界を与える。
【０３６２】
[00140]提案されるアルゴリズムに対する誤差分散に関する定理によれば、台検出に関して上記で説明した条件のもとで、また、雑音が、固定のｋおよびｎに関して台検出にかかわらず無相関であるという仮定のもとで、以下の条件が有効である。
【０３６３】
【数１１９】
0006495292.tif 000120
【０３６４】
ただし、
【０３６５】
【数１２０】
0006495292.tif 000121
【０３６６】
【数１２１】
0006495292.tif 000122
【０３６７】
である。
【０３６８】
[00141]上で提示された定理の有効性を立証するために、以下の３つの条件が満たされる必要がある。
【０３６９】
[00142]第１の条件は、
ｋ≦ｍとして、ｍ、およびｋがＡi,j〜Ｎ（０，１／ｍ）としてのｍ×ｋ行列Ａに対して与えられると、特異値ｓ1（Ａ）≧．．．≧ｓk（Ａ）は条件
【０３７０】
【数１２２】
0006495292.tif 000123
【０３７１】
を満たすことである。
【０３７２】
[00143]第２の条件は、
【０３７３】
【数１２３】
0006495292.tif 000124
【０３７４】
である。
【０３７５】
[00144]和集合上界により、
【０３７６】
【数１２４】
0006495292.tif 000125
【０３７７】
である。
【０３７８】
[00145]
【０３７９】
【数１２５】
0006495292.tif 000126
【０３８０】
がＬａｓｓｏ推定値として定義される。それは、最小２乗がＬａｓｓｏの台
【０３８１】
【数１２６】
0006495292.tif 000127
【０３８２】
に適用されることによって得られる。
【０３８３】
[00146]ＬＡＳＳＯ推定値は
【０３８４】
【数１２７】
0006495292.tif 000128
【０３８５】
と定義され、推定値は、最小２乗がＬＡＳＳＯの台
【０３８６】
【数１２８】
0006495292.tif 000129
【０３８７】
に、
【０３８８】
【数１２９】
0006495292.tif 000130
【０３８９】
【数１３０】
0006495292.tif 000131
【０３９０】
のように適用されることによって得られ、ここで、
【０３９１】
【数１３１】
0006495292.tif 000132
【０３９２】
である。
【０３９３】
[00147]引き続くすべてのウィンドウの中の台が正しく検出される場合、
【０３９４】
【数１３２】
0006495292.tif 000133
【０３９５】
となり、通常の最小２乗推定値は、
【０３９６】
【数１３３】
0006495292.tif 000134
【０３９７】
となる。
【０３９８】
[00148]
【０３９９】
【数１３４】
0006495292.tif 000135
【０４００】
の特異値が高い確率で非ゼロなので、行列
【０４０１】
【数１３５】
0006495292.tif 000136
【０４０２】
は可逆である。
【０４０３】
[00149]標準的なＬＳＥから、
【０４０４】
【数１３６】
0006495292.tif 000137
【０４０５】
である。
【０４０６】
[00150]ｎ回推定される信号における最初のエントリであるｖn-1＝ｘn-1などの、任意の固定のエントリに対して、
【０４０７】
【数１３７】
0006495292.tif 000138
【０４０８】
が与えられると、
【０４０９】
【数１３８】
0006495292.tif 000139
【０４１０】
【数１３９】
0006495292.tif 000140
【０４１１】
となる。
【０４１２】
[00151]ｍに関するこの値は、ほぼ１／ｎにつれて減少し、したがって、引き続くｎ個のウィンドウの中で台検出が成功する場合において、再構成分散はゼロへ進む。
【０４１３】
[00152]第３の場所では、前のケースの補完物
【０４１４】
【数１４０】
0006495292.tif 000141
【０４１５】
において、知る起こることが重要である。
【０４１６】
【数１４１】
0006495292.tif 000142
【０４１７】
および
【０４１８】
【数１４２】
0006495292.tif 000143
【０４１９】
に対して、上記の補助定理は、
【０４２０】
【数１４３】
0006495292.tif 000144
【０４２１】
をもたらす。
【０４２２】
[00153]したがって、
【０４２３】
【数１４４】
0006495292.tif 000145
【０４２４】
となる。
【０４２５】
[00154]三角不等式を使用すると、台集合におけるＬＳＥ推定値と真の信号との間の差の｀２−ノルムに対する上界を得る。
【０４２６】
【数１４５】
0006495292.tif 000146
【０４２７】
[00155]これらの結果を組み合わせることによって、得られるものは、
【０４２８】
【数１４６】
0006495292.tif 000147
【０４２９】
である。
【０４３０】
[00156]上式は、
【０４３１】
【数１４７】
0006495292.tif 000148
【０４３２】
および
【０４３３】
【数１４８】
0006495292.tif 000149
【０４３４】
に関する確率を使用し、ｖ、
【０４３５】
【数１４９】
0006495292.tif 000150
【０４３６】
、および
【０４３７】
【数１５０】
0006495292.tif 000151
【０４３８】
が、それぞれ、ｘ、
【０４３９】
【数１５１】
0006495292.tif 000152
【０４４０】
および
【０４４１】
【数１５２】
0006495292.tif 000153
【０４４２】
と交換され得ることに言及して、不等式１７を置き換えることによって得られる。
【０４４３】
[00157]以下において、再帰的な圧縮センシングのアルゴリズムの計算量が分析される。
【０４４４】
[00158]ｉがウィンドウインデックスである場合、Ａ(i)∈Ｒm×nはサンプリング行列であり、τは連続するウィンドウ間のスライディングステップのスライディングスロットの数を示し、第ｉのウィンドウの終わりまでにｎ＋（ｉ−１）τ個のエントリが復元されている。
【０４４５】
[00159]第１のウィンドウは、Ａ(0)ｘ(0)によってサンプリングされる。このことは、加算および乗算などのＯ（ｍｎ）回の基本演算を必要とする。初期ウィンドウの後、ウィンドウのサンプリング
【０４４６】
【数１５３】
0006495292.tif 000154
【０４４７】
は、複雑度Ｏ（ｍτ）を伴うランクｋの更新を有する再帰的なサンプリングによって実現される。したがって、第ｉのウィンドウの終わりまでに、サンプリングの総複雑度は、再帰的なサンプリングに関する平均複雑度としてのＯ（ｍτ）に対してＯ（ｍｎ）＋Ｏ（ｍτ）ｉとなる。
【０４４８】
[00160]計算量への他の寄与は、反復ソルバーから生じる。予期される複雑度は、各反復における演算の数に、収束を得るために予期される反復の数を掛けたものとして算出され得る反復ソルバーに起因する。前者は特定のアルゴリズムに依存し、後者は開始点の最適解までの距離の関数であり、再帰的な推定を使用するケースに次のように拘束される。
【０４４９】
[00161]
【０４５０】
【数１５４】
0006495292.tif 000155
【０４５１】
を使用する。
【０４５２】
[00162]開始点として、得られるものは、
【０４５３】
【数１５５】
0006495292.tif 000156
【０４５４】
である。
【０４５５】
[00163]上でなされた提示の有効性は、次のように証明される。
【０４５６】
【数１５６】
0006495292.tif 000157
【０４５７】
【数１５７】
0006495292.tif 000158
【０４５８】
【数１５８】
0006495292.tif 000159
【０４５９】
[00164]ノルムを取り出し三角不等式を使用することが、
【０４６０】
【数１５９】
0006495292.tif 000160
【０４６１】
をもたらす。
【０４６２】
[00165]Ｌａｓｓｏの誤差を与える定理への観点を用いると、得られるものは、
【０４６３】
【数１６０】
0006495292.tif 000161
【０４６４】
である。
【０４６５】
[00166]各反復の正確な計算量はアルゴリズムに依存する。最小限、ＬＡＳＳＯのための反復ソルバーは、サンプリング行列と、Ｏ（ｍｎ）回の演算を必要とする反復における推定値との乗算を必要とする。ＦＩＳＴＡにおけるように、費用関数がほぼ線形（たとえば、１／ｔ2）に減衰するアルゴリズムでは、
【０４６６】
【数１６１】
0006495292.tif 000162
【０４６７】
のような
【０４６８】
【数１６２】
0006495292.tif 000163
【０４６９】
を得るために必要とされる反復の数は、ｘ*を最適解として
【０４７０】
【数１６３】
0006495292.tif 000164
【０４７１】
に比例し、ここで、ｘ［０］はアルゴリズムの開始点である。この境界から、反復の平均の数が、アルゴリズムの開始点の最適点からのユークリッド距離に比例することが理解される。
【０４７２】
[00167]すべてのｉについて、Ｃ＞０を定数とし、‖ｘ(i)‖0≦ｋおよび
【０４７３】
【数１６４】
0006495292.tif 000165
【０４７４】
として、シーケンス｛ｘ1｝i=0,1,...に対して費用関数がほぼ線形に減衰するアルゴリズムの収束のために予期される反復の数は、雑音のない測定値に対して
【０４７５】
【数１６５】
0006495292.tif 000166
【０４７６】
であり、ｉ．ｉ．ｄ．の測定雑音に対して
【０４７７】
【数１６６】
0006495292.tif 000167
【０４７８】
である。
【０４７９】
[00168]上の記述は真である。というのも、ｘ(i)がｋ−スパースなので、項
【０４８０】
【数１６７】
0006495292.tif 000168
【０４８１】
および
【０４８２】
【数１６８】
0006495292.tif 000169
【０４８３】
は、式１８に従って消える。
【０４８４】
[00169]｜ｘi｜≦Ｃにより、
【０４８５】
【数１６９】
0006495292.tif 000170
【０４８６】
が得られる。
【０４８７】
[00170]雑音のある測定値に関して、項
【０４８８】
【数１７０】
0006495292.tif 000171
【０４８９】
は雑音レベルに関係する。雑音が分布Ｎ（０，σ2Ｉ）を有するので、高い確率で、
【０４９０】
【数１７１】
0006495292.tif 000172
【０４９１】
、したがって、ＬＡＳＳＯにおける誤差と関係する定理による前もっての条件によって、
【０４９２】
【数１７２】
0006495292.tif 000173
【０４９３】
となる。式（１８）におけるこの結果を使用すると、予期される反復の数が、雑音のあるケースにおいて
【０４９４】
【数１７３】
0006495292.tif 000174
【０４９５】
であることが見つけられる。
【０４９６】
[00171]上記の分析において、平均複雑度は、再帰的なサンプリングに対してＯ（ｍτ）であり、最適化アルゴリズムに対してＯ（ｍｎ）である（最小限で）。入力ストリームの各成分を復元するとともに要素を除外しないためにτ≦ｎであり、したがって、反復的な最適化の複雑度が平均複雑度を支配することが理解される。
【０４９７】
[00172]条件
【０４９８】
【数１７４】
0006495292.tif 000175
【０４９９】
を満たすために、単位球面からサンプリングされたランダムなベクトル、ランダムなガウス行列およびランダムなベルヌーイ行列に対して条件ｍ≧Ｃｋｌｏｇ（ｎ／ｋ）を使用することによる。以下の表１は、ｋにおける様々なスパース性の種類に関する平均計算量を示す。
【０５００】
【表１】
0006495292.tif 000176
【０５０１】
実験の結果
[00173]シミュレーションで使用されるデータは、ランダムモデル
【０５０２】
【数１７５】
0006495292.tif 000177
【０５０３】
から生成され、別段に述べられない限りｐ＝０．０５である。
【０５０４】
[00174]測定モデルは、
【０５０５】
【数１７６】
0006495292.tif 000178
【０５０６】
【数１７７】
0006495292.tif 000179
【０５０７】
【数１７８】
0006495292.tif 000180
【０５０８】
、サンプリング行列は、
【０５０９】
【数１７９】
0006495292.tif 000181
【０５１０】
であり、ただし、ｍは１つのウィンドウの中の非ゼロのエントリの予期される数の６倍、すなわち、ｍ＝６ｐｎであり、ここで、ｎはウィンドウの長さに等しい。
【０５１１】
[00175]ＬＡＳＳＯを解くためにＦＩＳＴＡ、加速された近接勾配法を使用しながら、所与のウィンドウを推定するために必要とされる平均時間を比較することによって、ＲＣＳによって達成される速度の向上がどのようなものなのかが、実験的に示されている。ＲＣＳはいわゆる「単純な手法」に対して比較され、ここで、サンプリングは各ウィンドウにおける行列乗算によって行われ、ＦＩＳＴＡはすべてゼロのベクトルから開始される。各ケースにおいて１つのウィンドウを復元するために必要とされる平均時間が、図２に示される。図２で観測され得るように、ＲＣＳに関する平均処理時間は、他の方法によって必要とされる処理時間よりも短い。
【０５１２】
[00176]ＬＡＳＳＯを使用する台推定における実験の結果が、本明細書とともに説明される。測定において、ｘ∈Ｒmx6000、‖ｘ‖0＝６０、Ａ∈Ｒm×6000が、Ａi,j〜Ｎ（０，１／ｍ）を伴うガウス分布によって生成され、ｗはσ＝０．１を有する。ＬＡＳＳＯ定理において示唆されるように、これらのパラメータに対して、ＬＡＳＳＯは、
【０５１３】
【数１８０】
0006495292.tif 000182
【０５１４】
を用いて解かれ、ｘの非ゼロの振幅はＵ（［−３．３４，−４：３４］Ｕ［３．３４，４．３４］）からサンプリングすることによって
【０５１５】
【数１８１】
0006495292.tif 000183
【０５１６】
を満たす。
【０５１７】
[00177]シミュレーションでは、取得されるサンプルの数は信号と異なり、ｍ、および台推定の精度が、＝｜検出された台∩真の台対｜／｜真の台｜に等しい検出率と、＝｜検出された台＼真の台｜／｜真の台｜であるフォールスポジティブの比率とを使用することによって検討され、ここで、｜．｜は集合の濃度を表し、＼は集合差分作用素である。この定義を用いると、フォールスポジティブの比率が１よりも大きくなり得ることに留意されたい。
【０５１８】
[00178]台検出のための２つの方法が比較される。第１の方法は、ＬＡＳＳＯを解き非ゼロの位置を台として採用することによるものであり、第２の方法は、推定値の絶対値がしきい値よりも大きい位置を採用することによるものである。図３は、ｍの各値に対して入力信号をランダムに２０回生成し、得られた検出率とフォールスポジティブとを平均することによって取得された、２つの方法に関して得られた曲線を示す。図から見られ得るように、検出率は両方の方法において同様に挙動するが、フォールスポジティブは、得られたＬＡＳＳＯ推定値へのしきい値を適切に調整することによって、著しく低減され得る。
【０５１９】
[00179]図３に詳細に示されるものは、ｎ＝６０００、σ＝０．１、ｍｉｎ｜ｘi｜≧３．３４、しきい値ξ1＝０．０１、０．１０、および１．００について、ＬＡＳＳＯを使用する台集合推定である。円形のマーカーは検出率を表し、正方形のマーカーはフォールスポジティブの比率を表す。
【０５２０】
[00180]上記で詳細に説明したように、ＬＡＳＳＯ法は、バイアスのない推定量をもたらすために、投票の方策および最小２乗推定と一緒に使用され得る。図４は、ａ）単一のＬＡＳＳＯ推定値、ｂ）平均された推定値、ｃ）投票の方策、およびｄ）バイアス除去および平均化の性能の比較を示す。
【０５２１】
[00181]図は、固定のｘ∈Ｒnを使用し、無相関の雑音を有する測定値を取り出すことによって得られる。誤差が、平均された推定値に対してゼロへ減少しないことが見られ得、それは、本明細書において前に説明したように、ＬＡＳＳＯがバイアスのある推定量であることに起因する。詳細には、図４は、ａ）平均された推定値、ｂ）バイアス除去および平均された推定値、ｃ）投票および平均化によって取得された推定値に関する、誤差プロットの描写である。
【０５２２】
[00182]次に図５を参照すると、図は、ストリーミングデータ上の平均されたＬＡＳＳＯ推定値ならびに「投票および平均化」に関する誤差プロットを示す。
【０５２３】
[00183]図５は、ストリーミングデータ上で、平均されたＬＡＳＳＯ推定値を用いて取得されたウィンドウ再構成誤差と、「投票および平均化」アルゴリズムを用いて取得されたウィンドウ再構成誤差との比較を示す。データはランダムに生成され、ここで、エントリはｐ＝０．０５を有する台として選択され、その振幅は、台検出定理の条件を満たすために一様分布
【０５２４】
【数１８２】
0006495292.tif 000184
【０５２５】
から独立同分布で引き出され、ｎ＝４００、ｍ＝５ｎｐ＝１００であり、サンプリング行列はガウス型である。測定は、
【０５２６】
【数１８３】
0006495292.tif 000185
【０５２７】
を用いて劣化させられ、ここで、σ＝０．０５であり、投票アルゴリズムはξ1＝０．５およびξ2＝２０を使用する。見られ得るように、投票は、ＬＳＥにおいてエントリを使用するために集められるべきξ2回の投票を待つことに起因する跳躍を示す再構成誤差を与える。しかしながら、位置が台の一部として認められた後、ＬＡＳＳＯ推定値を単に平均するよりも小さい値へ誤差が直ちに下落することも見られ得る。
【０５２８】
[00184]したがって、一実施形態に従って提案されるものは、ストリーミングデータ上の圧縮センシングに適切な、再帰的なサンプリングおよび反復的な復元のための効率のよい方法である。方法は、雑音の存在下で推定分散の低減を達成しながら、信号の推定値に対するより速い収束速度を達成する際に、連続する処理ウィンドウ間の信号のオーバーラップを活用する。
【０５２９】
[00185]さらに、別の実施形態によれば、信号のバイアスのない推定量をＬＡＳＳＯに基づいて近似するための２段階推定手順が提案され、その場合、ａ）台検出はＬＡＳＳＯを解くことによって実行され、また、ｂ）信号推定は推定される台集合で通常の最小２乗を解くことによって達成される。ｍを取得されるサンプルの数、ｎをウィンドウの長さとして、アルゴリズムの計算量はＯ（ｍｎ）である。収束時間は、ストリーミングデータ上のオンライン実装にとって適切であることが、実験によって示されている。
【０５３０】
[00186]したがって、要約すれば、実施形態は、ストリーミングデータの圧縮センシングのための方法を含み、方法は、ストリーミングデータ上で圧縮センシングを実行するための再帰的な方式を実行することを伴い、同様に、方法の計算量と推定誤差とを分析することができる。一実施形態によれば、次の測定値を取得する際に以前の測定値を利用しながら、データの入力ストリームが、オーバーラップするウィンドウ処理を解して再帰的にサンプリングされる。オーバーラップしたウィンドウ構造を活用すると、反復的な最適化アルゴリズムにおけるより速い収束を達成して新しいウィンドウを復号するために、以前のウィンドウからの信号推定値が利用される。推定精度は、複数のウィンドウから取得される信号推定値を平均することによって高められる。推定量のバイアスを除去するために、台集合検出と信号振幅推定とを備える一実施形態に従って、２段階推定手順が提案される。さらに、一実施形態は、大きい測定雑音の存在下でロバストな台推定を得るための投票方式を含む。
【０５３１】
[00187]ストリーミングデータの圧縮センシングのための一実施形態による手段を使用しながら取得されるシミュレーション結果は、信号の大きさおよび雑音レベルにおける軽い条件のもとで、著しく小さい再構成誤差を得ながら、従来の圧縮センシングをデータのストリームに適用することに対して１０倍の高速化を示す。
【０５３２】
[00188]別の実施形態によれば、ストリーミングデータを感知するための手段が、同様に提案される。ストリーミングデータを感知するための前記手段は、データの入力ストリームを再帰的にサンプリングするための手段と、後続の測定値を取得するために以前の測定値を使用するための手段とを備える。データの入力ストリームを再帰的にサンプリングするための手段は、少なくとも以前の測定値を取得するために、オーバーラップするウィンドウ処理のステップを使用することができる。
【０５３３】
[00189]一実施形態は、超広帯域信号を用いた測距を含む。たとえば、デバイスは、規則正しく送信されるスパイクへのリターンパルスを継続的に監視し得る（放射される信号が周期的である）。一般に、デバイスは、主エコーを、付加された複数のエコーを加えて受信する。デバイスが移動している場合、主エコーは、複数のエコーがするように、ある期間から別の期間へほんのわずかに変化する。これは周期的な信号でなく、まさにほぼ周期的な信号であり、スライディングウィンドウアルゴリズムは、これらのシフトしているエコーを当然のことながら追跡する。そのような実施形態では、音響センサからのエコーデータは、それによって距離データへと変換される。
【０５３４】
[00190]別の例では、生物医学的サンプルデータが、上述された方法およびシステムに従って変換され得る。たとえば、電気信号を人体から受信するように構成される１つまたは複数の電気センサからのサンプルは、心電図信号または脳波信号を再構成するために、本明細書での実施形態の開示に従って処理され得る。いくつかの実施形態では、再構成された信号は、１つまたは複数の診断条件に特徴的な兆候に一致することがある。
【０５３５】
[00191]別の例では、カメラ、光電、または他の画素アレイセンサ（たとえば、可視光または赤外光を受信するように構成される）からのサンプルデータが、本明細書で説明されるように処理され得る。たとえば、そのような技法を使用して、装置はまた、電力効率を改善することができ、またはセンサの感度を効果的に高めることができる。
【０５３６】
[00192]他の実施形態では、温度、風速、風向き、降水量などの環境センサのデータが、本明細書で説明されるように処理され得る。
【０５３７】
[00193]本発明の手段は、ソフトウェア手段、ハードウェア手段、またはそれらの組合せとして実装され得る。
【０５３８】
[00194]上述されたシステムおよび方法は、たとえば、そのようなモデムを組み込むワイヤレスモデムまたはワイヤレスデバイスで実施され得る。
【０５３９】
[00195]実施形態によっては、本明細書で説明された方法のうちいずれかの、いくつかの動作またはイベントは、異なる順序で実施されてよく、追加され、統合され、または完全に除外されてよい（たとえば、すべての説明した動作またはイベントが、本方法の実施のために必要であるとは限らない）ことを認識されたい。その上、いくつかの実施形態では、動作またはイベントは、連続してではなくむしろ、同時に、たとえば、マルチスレッド処理、割込み処理、または複数のプロセッサを通して実施され得る。
【０５４０】
[00196]本明細書で開示する方法、システムおよび装置と関連して説明する様々な例示的論理ブロック、モジュール、回路、およびアルゴリズムのステップは、電子ハードウェア、プロセッサによって実行されるコンピュータソフトウェア、または両方の組合せとして実装され得ることを、当業者は認識するであろう。ハードウェアとソフトウェアのこの互換性を明確に示すために、様々な例示的な構成要素、ブロック、モジュール、回路、およびステップは、全体的にそれらの機能性の点から上記に説明された。そのような機能性がハードウェアまたはソフトウェアとして実施されるかどうかは、特定の適用例および全体的なシステムに課せられた設計制約に依存する。当業者は、特定の適用例ごとに様々な方法で記載された機能を実装し得るが、そのような実装の決定が、本発明の範囲からの逸脱を引き起こすと解釈されるべきではない。
【０５４１】
[00197]その上、本明細書で開示する実施形態は、汎用プロセッサ、デジタル信号プロセッサ（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）もしくは他のプログラマブル論理デバイス、個別ゲートもしくはトランジスタロジック、個別ハードウェアコンポーネントなどの電子デバイスもしくは回路、または本明細書で説明した機能を実行するように設計されたそれらの任意の組合せを用いて実装または実施され得る。汎用プロセッサはマイクロプロセッサであり得るが、代替として、プロセッサは任意の従来のプロセッサ、コントローラ、マイクロコントローラ、またはステートマシンであり得る。プロセッサはまた、コンピューティングデバイスの組合せ、たとえば、ＤＳＰとマイクロプロセッサの組合せ、複数のマイクロプロセッサ、ＤＳＰコアと連携する１つまたは複数のマイクロプロセッサ、または任意の他のそのような構成として実施され得る。
【０５４２】
[00198]本明細書で開示する実施形態に関連して説明する方法またはアルゴリズムのステップは、ハードウェアで直接的に、プロセッサによって実行されるソフトウェアモジュールで、またはそれら２つの組合せで実施され得る。ソフトウェアモジュールは、ＲＡＭメモリ、フラッシュメモリ、ＲＯＭメモリ、ＥＰＲＯＭメモリ、ＥＥＰＲＯＭ（登録商標）メモリ、レジスタ、ハードディスク、リムーバブルディスク、ＣＤ−ＲＯＭ、または当技術分野で知られている任意の他の形態の記憶媒体に常駐し得る。例示的な記憶媒体は、プロセッサが記憶媒体から情報を読み取り、記憶媒体に情報を書き込むことができるようにプロセッサに結合される。代替として、記憶媒体はプロセッサと一体であり得る。プロセッサおよび記憶媒体は、ＡＳＩＣの中に存在してよい。ＡＳＩＣはユーザ端末の中に存在してよい。代替として、プロセッサおよび記憶媒体は、ユーザ端末の中で個別コンポーネントとして存在してよい。
【０５４３】
[00199]詳細には、本発明の一実施形態によれば、ストリーミングデータの圧縮センシングを実行するための装置は、データの入力ストリームを、入力データストリームに関する少なくとも１つの以前の測定値を取得するために、オーバーラップするウィンドウ処理を使用して再帰的にサンプリングするために構成された再帰的なサンプラーと、後続の測定値を取得するために、少なくとも１つの以前の測定値を使用するユニットとを備える。
【０５４４】
[00200]本発明の一実施形態に従って提案される装置は、感知することを実行するための再帰的な方式に基づく再帰的なサンプラーを備える。本発明のストリーミングデータの圧縮センシングを実行するための装置はまた、再帰的な推定を介した再帰的なサンプリングのステップの間にサンプリングされたデータとしての、ストリームを彼女が入力することを処理するための処理ユニットを備える。
【０５４５】
[00201]本発明によれば、ストリーミングデータの圧縮センシングを実行するための装置はまた、以前の推定値取得ステップの間に取得された以前の推定値のデータストリームに関する入力情報を受け渡すための記憶手段を備える。さらに、本発明のストリーミングデータの圧縮センシングを実行するための装置は、データストリームの台検出ステップの間に取得される情報に基づいて、回数推定を実行するために構成されたカウンタを備える。さらに、本発明の装置はまた、前記再帰的な推定ステップの間に取得されるデータに基づいて、データストリームの台の集合に対して最小２乗推定（ＬＳＥ）値を算出するための計算器を備えてよい。平均された値を取得するために平均された値を算出するために、算出された最小２乗推定値と、回数推定値と、以前の推定値とを平均するための処理ユニットは、本発明の一実施形態に従って提案される装置によって同様に備えられる。ストリーミングデータを感知するための方法の誤差の程度を推定するための推定器が、本発明に従って提案される装置によって備えられることが同様に想定される。加えて、複数のウィンドウから取得される信号推定値を平均するための処理ユニットは、本発明によって提案される装置によって同様に備えられてよい。
【０５４６】
[00202]様々な例が、記載された。これらおよび他の例は、以下の特許請求の範囲内である。
以下に、本願出願の当初の特許請求の範囲に記載された発明を付記する。
［Ｃ１］
ストリーミングデータの圧縮センシングを実行する方法であって、
データの入力ストリームを、前記入力データストリームに関する少なくとも１つの以前の測定値を取得するために、オーバーラップするウィンドウ処理を使用して再帰的にサンプリングすることと、
後続の測定値を取得するために、前記少なくとも１つの以前の測定値を使用することと
を備える方法。
［Ｃ２］
ストリーミングデータを感知するための前記方法は、前記サンプリングを実行するために再帰的な方式を使用する、Ｃ１に記載のストリーミングデータの圧縮センシングを実行するための方法。
［Ｃ３］
後続の測定値を取得するために前記少なくとも１つの以前の測定値を使用する前記ステップは、再帰的な推定を介した再帰的なサンプリングの前記ステップの間にサンプリングされたデータとしての、前記入力ストリームを処理することを備える、Ｃ１に記載のストリーミングデータの圧縮センシングを実行するための方法。
［Ｃ４］
前記データストリームに関する情報を受信することをさらに備え、ここにおいて、前記情報は、以前の推定値取得ステップの間に取得された以前の推定値に関係し、前記以前の推定値取得ステップは、前記再帰的なサンプリングステップの前に実行される、
Ｃ３に記載のストリーミングデータの圧縮センシングを実行するための方法。
［Ｃ５］
データストリームの台を検出することと、
前記データストリームの台検出ステップの間に取得される情報に基づいて、回数推定を実行することとをさらに備える、
Ｃ３に記載のストリーミングデータの圧縮センシングを実行するための方法。
［Ｃ６］
前記再帰的な推定ステップの間に取得されるデータに基づいて、データストリームの台の集合に対して最小２乗推定（ＬＳＥ）値を算出することをさらに備える、Ｃ３に記載のストリーミングデータの圧縮センシングを実行するための方法。
［Ｃ７］
平均された値を算出するために、前記算出された最小２乗推定値と、前記回数推定値と、前記以前の推定値とを平均することをさらに備える、Ｃ６に記載のストリーミングデータの圧縮センシングを実行するための方法。
［Ｃ８］
前記ストリーミングデータに対する新しい推定値を取得するために、前記平均された値を使用することをさらに備える、Ｃ７に記載のストリーミングデータの圧縮センシングを実行するための方法。
［Ｃ９］
ストリーミングデータの前記圧縮センシングの計算量を分析することをさらに備える、Ｃ１に記載のストリーミングデータの圧縮センシングを実行するための方法。
［Ｃ１０］
ストリーミングデータを感知するための前記方法の誤差の程度を推定することをさらに備える、Ｃ９に記載のストリーミングデータの圧縮センシングを実行するための方法。
［Ｃ１１］
新しいウィンドウを復号するために、反復的な最適化アルゴリズムにおいて収束を達成することをさらに備える、Ｃ１に記載のストリーミングデータの圧縮センシングを実行するための方法。
［Ｃ１２］
前記達成するステップは、オーバーラップするウィンドウ処理の前記ステップによって使用されるオーバーラップするウィンドウ構造と、前記以前のウィンドウに関する信号推定値とを活用することを備える、Ｃ１１に記載のストリーミングデータの圧縮センシングを実行するための方法。
［Ｃ１３］
複数のウィンドウから取得される信号推定値を平均することをさらに備える、Ｃ１に記載のストリーミングデータの圧縮センシングを実行するための方法。
［Ｃ１４］
台集合検出を実行することと、
信号振幅推定とをさらに備える、
Ｃ１３に記載のストリーミングデータの圧縮センシングを実行するための方法。
［Ｃ１５］
大きい測定雑音の存在下で、ロバストな台推定のために投票方式を適用することをさらに備える、Ｃ１に記載のストリーミングデータの圧縮センシングを実行するための方法。
［Ｃ１６］
ストリーミングデータの圧縮センシングを実行するためのシステムであって、複数のモジュールを含み、各モジュールは、
データの入力ストリームを、前記入力データストリームに関する少なくとも１つの以前の測定値を取得するために、オーバーラップするウィンドウ処理を使用して再帰的にサンプリングし、
後続の測定値を取得するために、前記少なくとも１つの以前の測定値を使用するための、
コンピュータ実行可能な命令をその上に有するコンピュータ可読媒体を備える、システム。
［Ｃ１７］
ストリーミングデータを感知するための、その上に記録されたコンピュータプログラムを有する非一時的コンピュータ可読記憶媒体であって、
前記コンピュータプログラムは、
データの入力ストリームを、前記入力データストリームに関する少なくとも１つの以前の測定値を取得するために、オーバーラップするウィンドウ処理を使用して再帰的にサンプリングし、
後続の測定値を取得するために、前記少なくとも１つの以前の測定値を使用することが可能なアルゴリズムを備える、
非一時的コンピュータ可読記憶媒体。
［Ｃ１８］
ストリーミングデータの圧縮センシングを実行するための装置であって、
センサデータの入力ストリームからのデータを記憶するように構成されたメモリと、
プロセッサとを備え、前記プロセッサは、
センサデータの入力ストリームを、前記入力データストリームに関する少なくとも１つの以前の測定値を取得するために、オーバーラップするウィンドウ処理を使用して再帰的にサンプリングし、
後続の測定値を取得するために、前記少なくとも１つの以前の測定値を使用するように構成される、
装置。
［Ｃ１９］
前記プロセッサは、前記感知することを実行するために、再帰的な方式に基づいて再帰的なサンプリングするように構成される、Ｃ１８に記載のストリーミングデータの圧縮センシングを実行するための装置。
［Ｃ２０］
前記プロセッサは、再帰的な推定を介した再帰的なサンプリングの前記ステップの間にサンプリングされたデータの前記入力ストリームを処理するようにさらに構成される、Ｃ１８に記載のストリーミングデータの圧縮センシングを実行するための装置。
［Ｃ２１］
以前の推定値取得ステップの間に取得された以前の推定値に関する前記データストリームに関する入力情報を受け渡すための記憶装置をさらに備える、Ｃ２０に記載のストリーミングデータの圧縮センシングを実行するための装置。
［Ｃ２２］
前記プロセッサは、データストリームの台検出ステップの間に取得される情報に基づいて、回数推定を実行するようにさらに構成される、Ｃ２０に記載のストリーミングデータの圧縮センシングを実行するための装置。
［Ｃ２３］
前記プロセッサは、前記再帰的な推定ステップの間に取得されるデータに基づいて、データストリームの台の集合に対して最小２乗推定（ＬＳＥ）値を実行するようにさらに構成される、Ｃ２０に記載のストリーミングデータの圧縮センシングを実行するための装置。
［Ｃ２４］
前記プロセッサは、平均された値を取得するために平均された値を算出するために、前記算出された最小２乗推定値と、前記回数推定値と、前記以前の推定値とを平均するようにさらに構成される、Ｃ２３に記載のストリーミングデータの圧縮センシングを実行するための装置。
［Ｃ２５］
前記プロセッサは、ストリーミングデータを感知するための前記方法の誤差の程度を平均するようにさらに構成される、Ｃ２４に記載のストリーミングデータの圧縮センシングを実行するための装置。
［Ｃ２６］
前記プロセッサは、複数のウィンドウから取得される信号推定値を平均するようにさらに構成される、Ｃ１８に記載のストリーミングデータの圧縮センシングを実行するための装置。
［Ｃ２７］
センサデータの前記ストリームを測定するように構成された１つまたは複数のセンサをさらに備える、Ｃ１８に記載の装置。
【図１】
0006495292.tif 000186
【図２】
0006495292.tif 000187
【図３】
0006495292.tif 000188
【図４】
0006495292.tif 000189
【図５】
0006495292.tif 000190