(57)【特許請求の範囲】
【請求項１】
信号（ｓ）の表現（ｙ）を決定するための方法であって、
所定の測定行列（Ｍ）から所定数（ｍ）の行ベクトル（ｖ１, ... ,ｖｍ）を選択するステップを有し、
前記所定の測定行列（Ｍ）は、所定のアダマール行列又は一般化アダマール行列（Ｈ）及び所定の表現行列（Ｂ）の積に依存して予め定められており、
前記信号（ｓ）及び前記選択された所定数（ｍ）の行ベクトル（ｖ１, ... ,ｖｍ）の各々の内積を決定することにより、前記信号（ｓ）の前記表現（ｙ）を形成する所定数（ｍ）の測定結果（ｙ１, ... ,ｙｍ）を獲得するステップをさらに有し、
前記所定数（ｍ）の行ベクトル（ｖ１, ... ,ｖｍ）及び前記所定数（ｍ）の測定結果（ｙ１, ... ,ｙｍ）を選択するステップが、前記所定の測定行列（Ｍ）の全ての行ベクトルの全ての要素から、前記所定数（ｍ）の行ベクトル（ｖ１, ... ,ｖｍ）及び前記所定数（ｍ）の測定結果（ｙ１, ... ,ｙｍ）をそれぞれ一様にランダムに選択することを含む、
方法。
【請求項２】
フーリエ行列が前記一般化アダマール行列（Ｈ）として使用される、請求項１に記載の方法。
【請求項３】
信号（ｓ）の表現（ｙ）を決定するための装置であって、
所定の測定行列（Ｍ）から所定数（ｍ）の行ベクトル（ｖ１, ... ,ｖｍ）を選択するように動作し、
前記所定の測定行列（Ｍ）は、所定のアダマール行列又は一般化アダマール行列（Ｈ）及び所定の表現行列（Ｂ）の積に依存して予め定められており、
前記信号（ｓ）及び前記選択された所定数（ｍ）の行ベクトル（ｖ１, ... ,ｖｍ）の各々の内積を決定することにより、前記信号（ｓ）の前記表現（ｙ）を形成する所定数（ｍ）の測定結果（ｙ１, ... ,ｙｍ）を獲得するようにさらに動作し、
前記所定数（ｍ）の行ベクトル（ｖ１, ... ,ｖｍ）及び前記所定数（ｍ）の測定結果（ｙ１, ... ,ｙｍ）を選択することが、前記所定の測定行列（Ｍ）の全ての行ベクトル及の全ての要素から、前記所定数（ｍ）の行ベクトル（ｖ１, ... ,ｖｍ）及び前記所定数（ｍ）の測定結果（ｙ１, ... ,ｙｍ）をそれぞれ一様にランダムに選択することを含む、
装置。
【請求項４】
プログラム命令を有する、信号（ｓ）の表現（ｙ）を決定するためのコンピュータ・プログラムであって、
前記プログラム命令が、コンピュータに、
所定の測定行列（Ｍ）から所定数（ｍ）の行ベクトル（ｖ１, ... ,ｖｍ）を選択するステップを実行させ、
前記所定の測定行列（Ｍ）は、所定のアダマール行列又は一般化アダマール行列（Ｈ）及び所定の表現行列（Ｂ）の積に依存して予め定められており、
前記プログラム命令が、前記コンピュータに、
前記信号（ｓ）及び前記選択された所定数（ｍ）の行ベクトル（ｖ１, ... ,ｖｍ）の各々の内積を決定することにより、前記信号（ｓ）の前記表現（ｙ）を形成する所定数（ｍ）の測定結果（ｙ１, ... ,ｙｍ）を獲得するステップをさらに実行させ、
前記所定数（ｍ）の行ベクトル（ｖ１, ... ,ｖｍ）及び前記所定数（ｍ）の測定結果（ｙ１, ... ,ｙｍ）を選択するステップが、前記所定の測定行列（Ｍ）の全ての行ベクトルの全ての要素から、前記所定数（ｍ）の行ベクトル（ｖ１, ... ,ｖｍ）及び前記所定数（ｍ）の測定結果（ｙ１, ... ,ｙｍ）をそれぞれ一様にランダムに選択することを含む、
コンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、信号の表現を決定するための方法、装置、コンピュータ・プログラム及びコンピュータ・プログラム製品に係り、さらに詳細に説明すれば、信号の圧縮表現に係る。
【背景技術】
【０００２】
アナログ信号の通常のキャプチャ及び処理は、２つのステップ、すなわちサンプル・ステップ及びその後の圧縮ステップから成る。もし、信号が帯域制限されていれば、サンプリングは、ナイキスト周波数、すなわち周波数範囲の２倍より若干高い周波数で行われる。その後の不可逆圧縮（例えば、画像用のＪＰＥＧ）は、大量の冗長情報を廃棄する。圧縮サンプリングは、信号を同時にサンプル及び圧縮するための新しく且つ有望な方法である。
【０００３】
非特許文献１には、圧縮サンプリングのための方法が記述されている。所与の基準の下でスパースである信号が、測定基準の下で非コヒーレントにサンプルされる。測定結果は、一様にランダムに獲得される。多数の測定結果は、当該信号の長さよりも遙かに小さい。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】E. J. Candes and M. Wakin: "An introduction to compressive sampling", IEEE SignalProcessing Magazine, 25:21-30, March 2008
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明の目的は、簡単で且つ効率的な、信号の表現を決定するための方法、装置、コンピュータ・プログラム及びコンピュータ・プログラム製品を提供することにある。
【課題を解決するための手段】
【０００６】
本発明の第１の側面に従って、信号ｓの表現ｙを決定するための方法、当該方法に対応する装置、コンピュータ・プログラム及びコンピュータ・プログラム製品が提供される。当該方法は、所定の測定行列Ｍから所定数ｍの行ベクトルｖ１, ... ,ｖｍを選択するステップを有する。所定の測定行列Ｍは、所定のアダマール行列又は一般化アダマール行列Ｈ及び所定の表現行列Ｂの積に依存して予め定められる。所定の表現行列Ｂは、信号ｓ用の所定の基準を表す。当該方法は、信号ｓ及び選択された所定数ｍの行ベクトルｖ１, ... ,ｖｍの各々の内積を決定することにより、所定数ｍの測定結果ｙ１, ... ,ｙｍを獲得するステップをさらに有する。所定数ｍの測定結果ｙ１, ... ,ｙｍは、信号ｓの表現ｙを形成する。当該装置は、当該方法を実施するように動作可能である。当該コンピュータ・プログラム製品は、当該方法を実施するようにコンピュータによって実行可能なプログラム命令を具体化するコンピュータ可読媒体を有する。当該装置は、コンピュータを有するか、又はコンピュータとして設計される。当該コンピュータ・プログラムは、当該方法を実施するのに適したプログラム命令を有する。当該コンピュータ・プログラムは、当該装置によって実行可能とすることができる。当該方法は、ハードウェアの形態、すなわち当該方法を実施するように特別に設計されるか又は当該方法を実施するのに適した回路として実装することができる。
【０００７】
第１の側面に関連する利点は、次のようなものである。すなわち、所定のアダマール行列又は一般化アダマール行列Ｈ及び所定の表現行列Ｂの積に依存して予め定められた所定の測定行列Ｍを使用することにより、所定の測定行列Ｍが、所定の表現行列Ｂに関して最大限に非コヒーレントになるということである。その結果、所定の測定行列Ｍに関して最大限の非コヒーレンスを持たない他の測定行列を使用する場合に比較してより小さくなるように、所定数ｍの測定結果ｙ１, ... ,ｙｍを予め定めることができる。従って、信号ｓの表現ｙを効率的にすることができる。さらに、当該方法は簡単である。このため、当該方法に対応する装置、コンピュータ・プログラム及びコンピュータ・プログラム製品も、簡単にすることができる。
【０００８】
本明細書の文脈では、「所定の」及び「予め定められる」という用語は、その対応する実体が本明細書に開示した方法の外部で決定され得ることを意味する。すなわち、当該実体は、本明細書に開示した方法に関して予め定められるが、必ずしも定数ではない。例えば、「所定数」という用語は、当該数が信号ｓに依存して決定されることを含むが、異なる信号については異なることがある。
【０００９】
本発明の第２の側面に従って、信号ｓの表現ｙを決定するための方法、当該方法に対応する装置、コンピュータ・プログラム及びコンピュータ・プログラム製品が提供される。当該方法は、信号ｓ用の所定の基準を表す所定の表現行列Ｂを信号ｓと乗算するか、又は信号ｓ用の所定の基準に基づく第１の変換アルゴリズムを信号ｓに適用することにより、信号ｓに依存する第１の変換ｂを決定するステップと、所定のアダマール行列若しくは一般化アダマール行列Ｈを信号ｓと乗算するか、又は第２の変換アルゴリズムとしてアダマール変換若しくは高速アダマール変換を信号ｓに適用することにより、第１の変換ｂに依存する第２の変換ｈを決定するステップと、第２の変換ｈから所定数ｍの測定結果ｙ１, ... ,ｙｍを選択するステップを有する。所定数ｍの測定結果ｙ１, ... ,ｙｍは、信号ｓの表現ｙを形成する。当該装置は、当該方法を実施するように動作可能である。当該コンピュータ・プログラム製品は、当該方法を実施するようにコンピュータによって実行可能なプログラム命令を具体化するコンピュータ可読媒体を有する。当該装置は、コンピュータを有するか、又はコンピュータとして設計される。当該コンピュータ・プログラムは、当該方法を実施するのに適したプログラム命令を有する。当該コンピュータ・プログラムは、当該装置によって実行可能とすることができる。当該方法は、ハードウェアの形態、すなわち当該方法を実施するように特別に設計されるか又は当該方法を実施するのに適した回路として実装することができる。
【００１０】
第２の側面に従った方法、装置、コンピュータ・プログラム及びコンピュータ・プログラム製品は、第１の側面に従った方法、装置、コンピュータ・プログラム及びコンピュータ・プログラム製品とそれぞれ本質的に同等である。第２の側面に関連する利点は、次のようなものである。すなわち、信号ｓ用の所定の基準に基づき第１の変換ｂを決定するとともに、所定のアダマール行列若しくは一般化アダマール行列Ｈ又はアダマール変換若しくは高速アダマール変換に基づき第２の変換を決定することにより、所定数ｍの測定結果ｙ１, ... ,ｙｍが、信号ｓ用の所定の基準に関して最大限に非コヒーレントである基準に関して獲得されるということである。その結果、信号ｓ用の所定の基準に関して最大限の非コヒーレンスを持たない他の測定行列を使用する場合に比較してより小さくなるように、所定数ｍの測定結果ｙ１, ... ,ｙｍを予め定めることができる。従って、信号ｓの表現ｙを効率的にすることができる。さらに、当該方法は簡単である。このため、当該方法に対応する装置、コンピュータ・プログラム及びコンピュータ・プログラム製品も、簡単にすることができる。
【００１１】
第１又は第２の側面の推奨実施形態によれば、一般化アダマール行列Ｈとしてフーリエ行列が使用される。その利点は、フーリエ行列を処理するための効率的で且つ高速の実装が存在するということである。従って、本方法は、ソフトウェアの形態だけでなく、ハードウェアの形態でも非常に効率的に実装することができる。他の利点は、フーリエ行列が任意のサイズで存在するため、任意の長さの信号を処理するのに適しているということである。
【００１２】
第１又は第２の側面の他の推奨実施形態によれば、所定数ｍの行ベクトルｖ１, ... ,ｖｍ又は所定数ｍの測定結果ｙ１, ... ,ｙｍを選択するステップは、所定の測定行列Ｍの全ての行ベクトル及び第２の変換ｈの全ての要素から、所定数ｍの行ベクトルｖ１, ... ,ｖｍ及び所定数ｍの測定結果ｙ１, ... ,ｙｍをそれぞれ一様にランダムに選択することを含む。その利点は、これが簡単であるということである。
【００１３】
第１又は第２の側面の他の推奨実施形態によれば、所定の表現行列Ｂ又は信号ｓ用の所定の基準は、スパース性（sparsity）ｋが信号ｓの長さｎより小さいとき、信号ｓがｋスパースであるか又は信号ｓ用の所定の基準の下で所定のしきい値に関してほぼｋスパースであるように選択される。その利点は、信号ｓ用の所定の基準に関して信号ｓのスパース性ｋがより小さくなるほど所定数ｍの測定結果ｙ１, ... ,ｙｍをより小さく予め定めることができるということである。好ましくは、スパース性ｋは、信号ｓの長さｎの１０パーセント未満であり、さらに好ましくは、信号ｓの長さの５パーセント未満である。従って、信号ｓの表現ｙは、特に効率的とすることができる。
【発明の効果】
【００１４】
本発明は、信号ｓの表現ｙを効率的にすることができることに加えて、信号ｓの表現ｙを決定するための方法、装置、コンピュータ・プログラム及びコンピュータ・プログラム製品を簡単にすることができるという効果を奏する。
【図面の簡単な説明】
【００１５】
【図１】信号ｓの表現ｙを決定するための方法の第１の実施形態を示す第１のフローチャートである。
【図２】信号ｓの表現ｙを決定するための方法の第２の実施形態の第２のフローチャートである。
【図３】所定の表現行列Ｂ、所定のアダマール行列Ｈ及び所定の測定行列Ｍを例示する図である。
【図４】信号ｓの表現ｙを決定するための装置ＤＥＶを例示する図である。
【発明を実施するための形態】
【００１６】
図１は、長さｎを有する信号ｓの表現ｙを決定するための方法及び当該方法に対応するコンピュータ・プログラムの第１の実施形態の第１のフローチャートを示す。当該方法は、「圧縮サンプリング」又は「圧縮センシング」と呼ばれる信号処理スキームに関係する。当該方法は、ステップｓ１で開始する。ステップｓ２では、所定の表現行列Ｂ、所定のアダマール行列若しくは一般化アダマール行列Ｈ及び／又は所定数ｍを選択又は決定する。特定のアプリケーションについては、これらは所与のものとすることができる。しかし、それらは、信号ｓの特性に依存して、決定又は選択することもできる。例えば、所定数ｍは、信号ｓに依存して決定することができ、従って異なる信号ｓについては異なることがある。すなわち、所定数ｍは、信号ｓに基づき適応的に決定することができる。
【００１７】
所定の表現行列Ｂは、信号ｓ用の所定の基準を表す。好ましくは、所定の表現行列Ｂは、ｎ×ｎのユニタリ行列（unitary matrix）である。好ましくは、信号ｓは、所定の基準の下でスパースであるか又はほぼスパースである。特に、スパース性ｋが信号ｓの長さｎより小さいとき、好ましくは信号ｓの長さｎより遙かに小さいとき、信号ｓは、所定の基準の下でｋスパースであるか又はほぼｋスパースである。その値のスパース性ｋがゼロである場合を除き、信号ｓは、所定の基準の下でｋスパースの展開を有する。その値のスパース性ｋが所定のしきい値未満の大きさを有する場合を除き、信号ｓは、所定の基準の下でほぼｋスパースの展開を有する。この所定のしきい値は、アプリケーションに依存して予め定めることができる。一般に、この所定のしきい値が予め定められるのは、当該所定のしきい値より下の値を無視することに起因する情報の損失が、当該アプリケーションに関して容認可能であるようにするためである。好ましくは、所定の基準の下の信号ｓの展開の少数の値を除く殆どの値は、ゼロであるか又は所定のしきい値未満の大きさを有する。好ましくは、スパース性ｋは、信号ｓの長さｎの１０パーセント未満であり、さらに好ましくは、信号ｓの長さｎの５パーセント未満である。その場合、信号ｓを有効に圧縮することができる。好ましくは、所定の表現行列Ｂは、単位行列（identity matrix）ではない。すなわち、任意のアダマール行列又は一般化アダマール行列Ｈ及び所定の表現行列Ｂの積は、この積の計算に使用されるアダマール行列又は一般化アダマール行列Ｈと常に異なることが好ましい。これと同じことは所定の表現行列Ｂに対応する変換、例えば第１の変換ｂについても当てはまる。好ましくは、この変換の出力は、常にその入力と異なる。
【００１８】
好ましくは、所定数ｍは、信号ｓの長さｎより小さくなるように予め定められ、さらに好ましくは、信号ｓの長さｎより遙かに小さくなるように予め定められる。好ましくは、所定数ｍは、スパース性ｋに依存して予め定められる、すなわち、スパース性ｋがより小さくなるほど所定数ｍをより小さく予め定めることができ、その逆も同様である。経験則として、所定数ｍは、スパース性ｋの約４倍となるように予め定めることができる。しかし、所定数ｍは、スパース性ｋの４倍より大きく又はスパース性ｋの１／４より小さくなるように予め定めることができる。所定数ｍは、信号ｓの表現ｙを形成する所定数ｍの測定結果ｙ１, ... ,ｙｍから信号ｓを復元するために使用される復元（reconstruction）アルゴリズムに依存して、又はアプリケーションに関する要件に依存して、これを予め定めることができる。
【００１９】
一般に、一般化アダマール行列は、Ｈ・Ｈ*＝ｎＩを満たし且つその全てのエントリが１（unity）の根である、ｎ×ｎの行列として定義される。この文脈では、Ｈ*は、一般化アダマール行列Ｈの共役転置（conjugate transpose）を表し、Ｉは、単位行列を表す。複素数ｗは、ｗｒ＝１である場合、１のｒ乗根と呼ばれる。一般に、アダマール行列は、その全てのエントリが実の値（＋１又は−１）を有する、一般化アダマール行列の特別のケースである、一般に、一般化アダマール行列は、信号ｓの全ての長さｎについて存在する。さらに、２又は４の倍数である信号ｓの長さｎについて、アダマール行列が存在するものと仮定される。２の累乗である長さｎについては、所定のアダマール行列Ｈは、シルベスター方法（Sylvester construction）を使用して容易に構築することができる。このシルベスター方法については、高速の実装が存在する。代替的に、信号ｓの長さｎがｑ＋１である場合には、ペイリー方法（Paley construction）を使用することができる。但し、ｑは、４を法として１又は３と合同である任意の素数冪である。すなわち、ある正の整数ｌ、素数ｐ及びｑ＝１（法４）又はｑ＝３（法４）について、ｑ＝ｐｌである。例えば、所定の一般化アダマール行列Ｈは、要素ｗｉｊを有するフーリエ行列とすることができる。但し、行はｉであり、列はｊ＝０, ...,ｎ−１であり、複素数ｗ＝ｃｏｓ（２π／ｎ）＋ｉ・ｓｉｎ（２π／ｎ）は、１のｉ・ｊ根である。しかし、所定の表現行列Ｂが単位行列である場合、所定の一般化アダマール行列Ｈは、フーリエ行列ではないことが好ましい。
【００２０】
ステップｓ３aでは、所定の測定行列Ｍが提供される。所定の測定行列Ｍは、信号ｓの表現ｙを形成する、所定数ｍの測定結果ｙ１, ... ,ｙｍを獲得するための所定の測定基準を表す。所定の測定行列Ｍは、所定のアダマール行列又は一般化アダマール行列Ｈ及び所定の表現行列Ｂに依存して予め定められる。特に、ステップｓ３ｂとして示されるように、所定の測定行列Ｍは、所定のアダマール行列又は一般化アダマール行列Ｈ及び所定の表現行列Ｂの積に依存して予め定められる。このようにすると、所定の測定行列Ｍは、所定の表現行列Ｂに関して最大限に非コヒーレントになる。このことは、任意の所定の表現行列Ｂに当てはまる。その結果、測定結果ｙ１, ... ,ｙｍの所定数ｍを最小にすることが可能となり、従って信号ｓの表現ｙを非常に効率的にすることができる。一般に、所定の測定行列Ｍがｎ×ｎのユニタリ行列である場合、所定の測定行列Ｍは、所定の表現行列Ｂであるｎ×ｎの他のユニタリ行列に対し最大限に非コヒーレントとなる。但し、ｓｑｒｔ（ｎ）Ｂ・ＭＴは、一般化アダマール行列であり、ｓｑｒｔ（ｎ）は、信号ｓの長さｎの平方根を表し、ＭＴは、所定の測定行列Ｍの転置を表すものとする。所定の測定行列Ｍ及び所定の表現行列Ｂの間のコヒーレンスは、行をｉ、ｊとするとき、１≦ｉ，ｊ≦ｎについて、μ（Ｂ, Ｍ）＝ｓｑｒｔ（ｎ）・ｍａｘ｜ｕｊ, ｖｉ｜として定義することができる。すなわち、コヒーレンスは、所定の表現行列Ｂの行ベクトルｕｊ及び所定の測定行列Ｍの行ベクトルｖｉの全ての内積の最大の絶対値である。言いかえれば、コヒーレンスは、所定の表現行列Ｂの任意の２つの行ベクトルｕｊ，ｖｉ及び所定の測定行列Ｍの間の最大の相関性を測定する手段である。従って、コヒーレンスが最小である場合に、最大のインコヒーレンスが達成される。
【００２１】
ステップｓ４では、信号ｓが提供される。ステップｓ５では、所定の測定行列Ｍの全ての使用可能な行ベクトルｖｉから、所定の測定行列Ｍの所定数ｍの行ベクトルｖ１, ... ,ｖｍが選択される。ステップｓ６では、信号ｓ及び所定数ｍの行ベクトルｖ１, ... ,ｖｍの各々の内積がそれぞれ決定される。これらの内積の各々は、信号ｓの表現ｙを形成する、所定数ｍの測定結果ｙ１, ... ,ｙｍのうちの１つを形成する。好ましくは、所定数ｍは、信号ｓの長さｎより小さく、特にその長さｎより遙かに小さいから、一般に、信号ｓの表現ｙは、信号ｓの圧縮表現ｙとなる。この方法は、ステップｓ７で終了する。
【００２２】
所定の測定行列Ｍの所定数ｍの行ベクトルｖ１, ... ,ｖｍを選択することは、ランダムに、好ましくは、一様にランダムに行うことができる。代替的に、この選択は、異なった態様で、例えば、復元アルゴリズムの諸要件に依存して行うことができる。
【００２３】
図２は、長さｎを有する信号ｓの表現ｙを決定するための方法及び当該方法に対応するコンピュータ・プログラムの第２の実施形態の第２のフローチャートを示す。この第２の実施形態は、第１の実施形態と本質的に同等である。相違点は、所定の測定行列Ｍが直接的に使用されないこと、所定の表現行列Ｂ及び所定のアダマール行列若しくは一般化アダマール行列Ｈ又はそれぞれの変換アルゴリズムが別々に順次に適用されることである。この方法は、ステップｓ１０で開始する。ステップｓ１１は、ステップｓ２（図１）に対応する。ステップｓ１２は、ステップｓ４（図１）に対応する。
【００２４】
ステップｓ１３では、第１の変換ｂが決定される。図２には、その２つの代替法が示されている。第１の代替法では、第１の変換ｂは、所定の表現行列Ｂ及び信号ｓを乗算することにより、信号ｓに依存して決定される。第２の代替法では、第１の変換ｂは、所定の表現行列Ｂに基づく第１の変換アルゴリズムｔｒａｎｓ（ｓ, Ｂ）を信号ｓに適用することにより、信号ｓに依存して決定される。例えば、第１の変換アルゴリズムｔｒａｎｓ（ｓ, Ｂ）は、離散コサイン変換又はウェーブレット変換、特に高速ウェーブレット変換を含むことができる。しかし、他の第１の変換アルゴリズムｔｒａｎｓ（ｓ, Ｂ）を選択することもできる。第１及び第２の代替法は、互いに同等であるが、ソフトウェア及びハードウェアの何れの形態においても高速の実装が存在するという理由で、第２の代替法の方が好ましい。
【００２５】
ステップｓ１４では、第２の変換ｈが決定される。図２には、その２つの代替法が示されている。第１の代替法では、第２の変換ｈは、所定のアダマール行列又は一般化アダマール行列Ｈ及び第１の変換ｂを乗算することにより、第１の変換ｂに依存して決定される。第２の代替法では、第２の変換ｈは、所定のアダマール行列又は一般化アダマール行列Ｈに基づく第２の変換アルゴリズムｔｒａｎｓｆ（ｂ, Ｈ）を第１の変換ｂに適用することにより、第１の変換ｂに依存して決定される。例えば、第２の変換アルゴリズムｔｒａｎｓｆ（ｂ, Ｈ）は、アダマール変換、高速アダマール変換、離散フーリエ変換又は高速フーリエ変換を含むことができる。しかし、他の第２の変換アルゴリズムｔｒａｎｓｆ（ｂ, Ｈ）を選択することもできる。第１及び第２の代替法は、互いに同等であるが、ソフトウェア及びハードウェアの何れの形態においても高速の実装が存在するという理由で、第２の代替法の方が好ましい。
【００２６】
ステップｓ１３及びｓ１４では、ステップｓ１３の第１の代替法をステップｓ１４の第１又は第２の代替法と組み合わせることができる。同様に、ステップｓ１３の第２の代替法をステップｓ１４の第１又は第２の代替法と組み合わせることができる。
【００２７】
ステップｓ１５では、第２の変換ｈから所定数ｍの測定結果ｙ１, ... ,ｙｍが選択される。第２の変換ｈの所定数ｍの測定結果ｙ１, ... ,ｙｍの選択は、ランダムに、好ましくは一様にランダムに行うことができる。しかし、この選択は、異なる態様で、例えば復元アルゴリズムの諸要件に依存して行うことができる。
【００２８】
図１及び図２を参照して説明した方法は、コンピュータによって実行可能なプログラム命令を有するコンピュータ・プログラムとして実装することができる。装置ＤＥＶは、当該コンピュータ・プログラムのプログラム命令を実行するためのコンピュータを有することができる。代替的に、当該コンピュータ・プログラムは、オペレーティング・システム又はコンピュータ・システムの基本入出力システムの一部とすることができる。コンピュータ可読媒体は、当該装置ＤＥＶ又はコンピュータ・システムによって実行可能なプログラム命令を具体化して提供することができる。例えば、コンピュータ可読媒体は、ＣＤ−ＲＯＭ、フラッシュ・メモリ・カード、ハード・ディスク又は他の適切なコンピュータ可読媒体とすることができる。しかし、図１及び図２を参照して説明した方法は、ハードウェアの形態で、例えばこの方法を実施するように特別に設計された信号処理ユニットＳＰＵとして実装することもできる。
【００２９】
図３は、信号ｓの長さｎが４に等しい場合の、所定の表現行列Ｂ、所定のアダマール行列Ｈ及び結果的に得られる所定の測定行列Ｍを例示する。この例では、所定の表現行列Ｂは、４×４のハー行列（Haar matrix）として予め定められる。所定の測定行列Ｍの行ベクトルｖｉの各々は、破線ボックス内に示される。所定の測定行列Ｍは、所定の表現行列Ｂに関して最大限に非コヒーレントである。代替的に、所定の表現行列Ｂ及び／又は所定のアダマール行列若しくは一般化アダマール行列Ｈは、異なった態様で予め定めることができる。一般に、信号ｓの長さｎは、実際的な殆どのケースにおいて、４よりも大きいであろう。
【００３０】
図４は、装置ＤＥＶを例示する。装置ＤＥＶは、少なくとも１つの処理ユニットＣＰＵ及び少なくとも１つの記憶ユニットＭＥＭを有することができる。本方法のプログラム命令を有するコンピュータ・プログラムは、記憶ユニットＭＥＭにロード又は格納され、処理ユニットＣＰＵによって実行することができる。これに加えて又はその代わりに、本方法を実施するために信号処理ユニットＳＰＵを提供することができる。信号ｓを提供するために、少なくとも１つの信号源ＳＲＣが処理ユニットＣＰＵ又は信号処理ユニットＳＰＵに結合される。少なくとも１つの信号源ＳＲＣは、装置ＤＥＶの外部又は内部に配置され、センサを有することができる。好ましくは、装置ＤＥＶは、少なくとも１つの入出力ユニットＩＯを有する。２つ以上の装置ＤＥＶを提供し、それぞれの入出力ユニットＩＯを介して通信のために結合することができる。例えば、少なくとも１つの装置ＤＥＶは、少なくとも１つの信号ｓの表現ｙを決定し、この表現ｙを入出力ユニットＩＯを介して他の装置ＤＥＶ（例えば、主又は中央装置ＤＥＶ）に送信する。信号ｓの圧縮表現ｙは、信号ｓそれ自体と比較して、非常に効率的に送信することができる。送信に加えて又はその代わりに、信号ｓの表現ｙは、例えば、少なくとも１つの記憶ユニットＭＥＭ内に、非常に効率的に格納することができる。
【００３１】
一実施形態では、少なくとも１つの信号源ＳＲＣは、少なくとも１つの処理ユニットＣＰＵ内に配置され、例えば、カウンタとして設計することができる。それぞれのカウンタの値、例えば信号ｓは、それぞれの処理ユニットＣＰＵ及び／又は装置ＤＥＶの性能モニタのために使用することができる。圧縮サンプリングは、マルチコア・システム、すなわち処理ユニットＣＰＵ当たり少なくとも２つの処理コアを備えるか又は少なくとも１つの処理コアを有する少なくとも２つの処理ユニットＣＰＵを備えるシステム内で、性能情報を効率的に収集するために使用することができる。最近の処理ユニットＣＰＵは、達成することが困難な特定のコード部分の実行について実際の平均ＣＰＩ（clock cycles per instruction）を予測する、複数の相互作用部分を含んでいる。このことは、処理ユニットＣＰＵに対する追加のユニット、すなわち処理ユニットＣＰＵの残りの性能をサンプルする性能モニタ・ユニットの導入につながった。最近の性能モニタ・ユニットは、バスの使用量、キャッシュ・ミス、ページ・フォルト、分岐ミス等を示すための数百ものカウンタに加えて、多数のパイプライン命令及び予測ブランチのうちどれがカウンタを実際に増加させるかを決定するための複雑な論理を含むことがある。個別の処理ユニットＣＰＵ上の性能モニタ・ユニットは、タスク・スケジューラに情報を供給する必要がある。さらに、性能モニタ・ユニットの論理は、それらが占めるコアの量を減らすように簡単に保たれなければならない。というのは、それらからデータを抽出するソフトウェアは、過剰なサイクルを消費してはならないし、当該データの分配は、過剰なメモリ帯域幅を使用してはならないからである。特に、このことが当てはまるのは、１つの処理ユニットＣＰＵ上で稼働する特定の中央タスク・スケジューラ上に当該データが収集され且つ処理される場合である。最近のパスにおけるスレッドの振る舞いが現在のパスに類似する可能性が高いために、性能モニタ・ユニットからのデータは、高度に構造化されていると予測されるであろう。従って、それは圧縮可能でなければならない。標準的な圧縮技術を使用していたのでは、性能モニタ・ユニット上のストレージの量を増加させずに、しかもタスク・スケジューリングの要請に不適当な遅延を導入することなしに、圧縮を達成することは困難であろう。もし、信号ｓの性質が知られていれば、その最も重要な側面だけをサンプルすることにより、信号ｓの直接的に圧縮された表現ｙを獲得することが可能である。それぞれの処理ユニットＣＰＵの平均ＣＰＩは、例えば、一命令を実行するのに必要なある期間にわたるサイクルの平均数を表す。実際の平均ＣＰＩは、離散的であるが、それが変わるレートは、時間の連続関数と見なすことができる任意の現実的なサンプリング期間よりも遙かに速い。圧縮サンプリングは、信号ｓとしてのこの実際の平均ＣＰＩの圧縮された表現ｙを決定するために使用することができる。その結果、性能モニタ・ユニットを簡単にするとともに、格納及び帯域幅のための諸要件を低くすることができる。
【００３２】
他のアプリケーションは、ストリーミング・データベース内でクエリを実行する等の、ストリーミング的に扱われるデータを処理することに対処する。大量のデータが関係している場合、これは困難な動作であり得る。これが問題となって現れるのは、例えば、ネットワーク・データ情報を扱う際に、典型的な問題が「ヘビーヒッター（heavy-hitter）」、すなわち大量のトラフィックの原因であるトップ・フローのリストを返す場合である。他の重要な領域は、株式及び外国為替相場の記憶及び分析のような金融市場である。任意のストリーミング・データベース・システムでは、データ収集（何をどのように保存するか）及びクエリ機構（収集されたものの探索）がある。圧縮サンプリング又はその変形は、何を保存し且つこれをどのように探索するかを決定するための有望な技術である。
【００３３】
さらに、圧縮サンプリングは、核磁気共鳴映像法（ＭＲＩ）、一般カメラ・センサ・デバイス等の多数の画像アプリケーション、又は音声処理におけるアプリケーションを有する。従って、圧縮サンプリングを使用すると、新しいカメラ、医学用の画像装置、セキュリティ・スキャナ又は音声を記録及びサンプルするための新しいアルゴリズムを有する音声装置の開発が可能になる。他のアプリケーションは、アナログＩ／Ｏに関して、通信システム及びネットワーキングにおいて、特にセンサ・ネットワークにおいて、可能であるだろう。他のアプリケーションも可能であるだろう。また、圧縮サンプリングを使用すると、装置ＤＥＶの電力消費量を減少させることが可能になる。というのは、サンプルを計算可能な効率的な態様で行うことができるばかりか、必要とされるサンプルの量を最適に最小にすることができるからである。
【符号の説明】
【００３４】
ｓ・・・信号
ｙ・・・信号ｓの表現
ｎ・・・信号ｓの長さ
ｍ・・・所定数
Ｂ・・・所定の表現行列
Ｈ・・・所定のアダマール行列又は一般化アダマール行列
Ｍ・・・所定の測定行列
（ｖ１, ... ,ｖｍ）・・・所定数ｍの行ベクトル
（ｙ１, ... ,ｙｍ）・・・所定数ｍの測定結果
ｂ・・・第１の変換
ｈ・・・第２の変換
（ｔｒａｎｓｆ（ｓ, Ｂ））・・・第１の変換アルゴリズム
（ｔｒａｎｓｆ（ｂ, Ｈ））・・・第２の変換アルゴリズム
ＤＥＶ・・・装置
ＣＰＵ・・・処理ユニット
ＭＥＭ・・・記憶ユニット
ＳＰＵ・・・信号処理ユニット
ＳＲＣ・・・信号源
ＩＯ・・・入出力ユニット
【図１】
0005385986.tif 000002
【図２】
0005385986.tif 000003
【図３】
0005385986.tif 000004
【図４】
0005385986.tif 000005