(57)【特許請求の範囲】
【請求項１】
ａ．長さＭの測定ベクトルｙを獲得するために、Ｍ×Ｎ測定行列Ａを用いて、長さＮのスパース信号ベクトルｘ＝｛ｘｉ｝に対して線形測定を実行するステップであって、前記測定行列Ａが、
【数１】
0005693750.tif 000108
によって表され、
ここで、ｄ＝１〜Ｄである場合、ＡｄΠｄは、前記測定行列Ａの部分行列であり、Πｄは、Ｎ×Ｎランダム置換行列であり、Ａｄは、
【数２】
0005693750.tif 000109
によって表されるＪ×Ｎ行列であり、
ここで、Ｍ＜＜Ｎ、Ｊ×Ｌ＝Ｎであり、同じ置換行列から生成された測定シンボルは、１つの次元と呼ばれ、Ｄは、総次元数である、ステップと、
ｂ．前記長さＮのスパース信号ベクトルｘ＝｛ｘｉ｝を前記長さＭの測定ベクトルｙから回復するステップと
を含む、スパース信号を測定および回復するための方法。
【請求項２】
前記スパース信号が、デジタル・スパース信号であり、前記スパース信号ベクトルｘ内の各成分ｘｉが、有限集合Ｑ＝｛Ｘ０＝０，Ｘ１，．．．，ＸＱ−１｝から取られ、ｑ＝１〜Ｑ−１の場合、Ｘｑはゼロ以外の数であり、Ｑは前記集合のサイズである場合、前記ステップｂが、
ｂ１．Ｄ個の次元に対してそれぞれ最尤検出を実行するために、Ｄ個の最尤検出器を使用するステップであって、第ｄの最尤検出器が、第ｄの次元に対して最尤検出を実行するために使用される、ステップと、
ｂ２．所定の条件が満たされるまで、ステップｂ１を複数回反復して繰り返すステップと、
ｂ３．最後の反復における第Ｄの最尤検出器の出力に基づいて、前記スパース信号ベクトル内の原シンボルを推定するステップと
を含む、請求項１に記載の方法。
【請求項３】
前記ステップｂ１が、
第ｄの次元について、前記スパース信号ベクトル内の前記原シンボルについての事後情報を生成するために、第ｄの次元の測定シンボルと第ｄの次元における先行情報とに基づいて、最尤検出を実行するステップであって、第ｄの次元において生成される前記事後情報が、第（ｍｏｄ（ｄ，Ｄ）＋１）の次元における先行情報を更新するために使用される、ステップ
を含む、請求項２に記載の方法。
【請求項４】
第ｄの次元における事後情報ｐ（ｄ）（ｘｉ＝Ｘｑ）が、第（ｍｏｄ（ｄ，Ｄ）＋１）の次元における先行情報
【数３】
0005693750.tif 000110
を、以下の式
【数４】
0005693750.tif 000111
によって更新するために使用され、ここで、ｅ（ｍｏｄ（ｄ，Ｄ）＋１）（ｘｉ＝Ｘｑ）は、先行する反復の第（ｍｏｄ（ｄ，Ｄ）＋１）の次元において生成され、これは、ｑ＝０〜Ｑ−１の場合、第（ｍｏｄ（ｄ，Ｄ）＋１）の次元におけるｘｉがＸｑである外部確率を表し、ｅ（ｍｏｄ（ｄ，Ｄ）＋１）（ｘｉ＝Ｘｑ）は、第１の反復において１に初期化され、後続する反復において
【数５】
0005693750.tif 000112
のように更新される、請求項３に記載の方法。
【請求項５】
前記スパース信号が、アナログ・スパース信号である場合、前記ステップｂが、
ｂ１．ｄ＝１〜Ｄ、ｊ＝１〜Ｊの場合、
【数６】
0005693750.tif 000113
内の各要素
【数７】
0005693750.tif 000114
について、
【数８】
0005693750.tif 000115
が０に等しいかどうかを判断するステップであって、
【数９】
0005693750.tif 000116
が、
【数１０】
0005693750.tif 000117
と初期化され、
【数１１】
0005693750.tif 000118
が、
【数１２】
0005693750.tif 000119
の第ｄの次元内の第ｊの要素である、ステップと、
ｂ２．
【数１３】
0005693750.tif 000120
が０に等しい場合、ｌ＝１〜Ｌとして、
【数１４】
0005693750.tif 000121
と設定するステップであって、
ここで、Πｄ（ｉ）は、第ｄの置換結果におけるｘｉのインデックスであり、
【数１５】
0005693750.tif 000122
は、Πｄ（ｉ）の逆操作である、ステップと
を含み、
前記ステップｂが、さらに
ｂ３．ｉ＝１〜Ｎの場合、前記スパース信号ベクトルｘ内の各原シンボルｘｉについて、以下の式
【数１６】
0005693750.tif 000123
が満たされるかどうかを判断するステップと、
ｂ４．上記の式が（ｄｍ，ｄｎ）のペアについて満たされる場合、
【数１７】
0005693750.tif 000124
と設定するステップであって、
ここで、
【数１８】
0005693750.tif 000125
および
【数１９】
0005693750.tif 000126
である、ステップと
を含み、
上記のステップｂ１〜ｂ４の後、前記ステップｂが、さらに
ｂ５．回復されたスパース信号を、以下の式
【数２０】
0005693750.tif 000127
によって、測定ベクトルｙから減算することによって、
【数２１】
0005693750.tif 000128
を更新するステップであって、
ここで、
【数２２】
0005693750.tif 000129
は、未回復シンボルが０に設定された、回復されたスパース信号ベクトルを表す、ステップと、
ｂ６．所定の条件が満たされるまで、上記のステップｂ１〜ｂ５を複数回反復して繰り返すステップと
を含む、請求項１に記載の方法。
【請求項６】
前記所定の条件が、以下のいずれか、すなわち、
−一定の反復回数に達した、
−２つの連続する反復において第Ｄの最尤検出器において生成された事後確率の間の差が事前定義された閾値を下回った
を含む、請求項２に記載の方法。
【請求項７】
前記所定の条件が、以下のいずれか、すなわち、
−一定の反復回数に達したこと、
−前記スパース信号ベクトル内のすべての原シンボルの回復に成功したこと、
−
【数２３】
0005693750.tif 000130
、ここで、
【数２４】
0005693750.tif 000131
および
【数２５】
0005693750.tif 000132
は、１つの反復の前後の
【数２６】
0005693750.tif 000133
を表すこと
を含む、請求項５に記載の方法。
【請求項８】
長さＭの測定ベクトルｙを獲得するために、Ｍ×Ｎ測定行列Ａを用いて、長さＮのスパース信号ベクトルｘ＝｛ｘｉ｝に対して線形測定を実行するための測定手段であって、前記測定行列Ａが、
【数２７】
0005693750.tif 000134
によって表され、
ここで、ｄ＝１〜Ｄの場合、ＡｄΠｄは、前記測定行列Ａの部分行列であり、Πｄは、Ｎ×Ｎランダム置換行列であり、Ａｄは、
【数２８】
0005693750.tif 000135
によって表されるＪ×Ｎ行列であり、
ここで、Ｍ＜＜Ｎ、Ｊ×Ｌ＝Ｎであり、同じ置換行列から生成された測定シンボルは、１つの次元と呼ばれ、Ｄは、総次元数である、測定手段と、
前記長さＮのスパース信号ベクトルｘ＝｛ｘｉ｝を前記長さＭの測定ベクトルｙから回復するための回復手段と
を備える、スパース信号を測定および回復するための装置。
【請求項９】
前記スパース信号が、デジタル・スパース信号であり、前記スパース信号ベクトルｘ内の各成分ｘｉが、有限集合Ｑ＝｛Ｘ０＝０，Ｘ１，．．．，ＸＱ−１｝から取られ、ｑ＝１〜Ｑ−１の場合、Ｘｑは、ゼロ以外の数であり、Ｑは、前記集合のサイズである場合、前記回復手段が、
Ｄ個の次元に対してそれぞれ最尤検出を実行するためのＤ個の最尤検出器を含む検出手段であって、第ｄの最尤検出器が、第ｄの次元に対して最尤検出を実行するために使用され、
前記検出手段が、所定の条件が満たされるまで、上述の最尤検出を複数回反復して繰り返す、検出手段と、
最後の反復における第Ｄの最尤検出器の出力に基づいて、前記スパース信号ベクトル内の原シンボルを推定するための推定手段と
を備える、請求項８に記載の装置。
【請求項１０】
第ｄの次元について、前記検出手段内の前記第ｄの最尤検出器が、前記スパース信号ベクトル内の前記原シンボルについての事後情報を生成するために、第ｄの次元の測定シンボルと第ｄの次元における先行情報とに基づいて、最尤検出を実行するために使用され、第ｄの次元において生成される前記事後情報が、第（ｍｏｄ（ｄ，Ｄ）＋１）の次元における先行情報を更新するために使用される、請求項９に記載の装置。
【請求項１１】
第ｄの次元における事後情報ｐ（ｄ）（ｘｉ＝Ｘｑ）が、第（ｍｏｄ（ｄ，Ｄ）＋１）の次元における先行情報
【数２９】
0005693750.tif 000136
を、以下の式
【数３０】
0005693750.tif 000137
によって更新するために使用され、ここで、ｅ（ｍｏｄ（ｄ，Ｄ）＋１）（ｘｉ＝Ｘｑ）は、先行する反復の第（ｍｏｄ（ｄ，Ｄ）＋１）の次元において生成され、これは、ｑ＝０〜Ｑ−１の場合、第（ｍｏｄ（ｄ，Ｄ）＋１）の次元におけるｘｉがＸｑである外部確率を表し、ｅ（ｍｏｄ（ｄ，Ｄ）＋１）（ｘｉ＝Ｘｑ）は、第１の反復において１に初期化され、後続する反復において
【数３１】
0005693750.tif 000138
のように更新される、請求項１０に記載の装置。
【請求項１２】
前記スパース信号が、アナログ・スパース信号である場合、前記回復手段が、
ｄ＝１〜Ｄ、ｊ＝１〜Ｊの場合に、
【数３２】
0005693750.tif 000139
内の各要素
【数３３】
0005693750.tif 000140
について、
【数３４】
0005693750.tif 000141
が０に等しいかどうかを判断するための判断手段であって、
【数３５】
0005693750.tif 000142
が、
【数３６】
0005693750.tif 000143
と初期化され、
【数３７】
0005693750.tif 000144
が、
【数３８】
0005693750.tif 000145
の第ｄの次元内の第ｊの要素であり、
【数３９】
0005693750.tif 000146
が０に等しい場合、ｌ＝１〜Ｌとして、
【数４０】
0005693750.tif 000147
と設定し、
ここで、Πｄ（ｉ）は、第ｄの置換結果におけるｘｉのインデックスであり、
【数４１】
0005693750.tif 000148
は、Πｄ（ｉ）の逆操作であり、
ｉ＝１〜Ｎの場合に、前記スパース信号ベクトルｘ内の各原シンボルｘｉについて、以下の式
【数４２】
0005693750.tif 000149
が満たされるかどうかを判断し、
上記の式が（ｄｍ，ｄｎ）のペアについて満たされる場合、
【数４３】
0005693750.tif 000150
と設定し、
ここで、
【数４４】
0005693750.tif 000151
および
【数４５】
0005693750.tif 000152
である、判断手段と、
回復されたスパース信号を、以下の式
【数４６】
0005693750.tif 000153
によって、測定ベクトルｙから減算することによって、
【数４７】
0005693750.tif 000154
を更新するための更新手段であって、
ここで、
【数４８】
0005693750.tif 000155
は、未回復シンボルが０に設定された、回復されたスパース信号ベクトルを表し、
前記判断手段が、所定の条件が満たされるまで、上記の判断を複数回反復して繰り返す、更新手段と
を備える、請求項８に記載の装置。
【請求項１３】
前記所定の条件が、以下のいずれか、すなわち、
−一定の反復回数に達したこと、
−２つの連続する反復において生成された事後確率の間の差が事前定義された閾値を下回ったこと
を含む、請求項９に記載の装置。
【請求項１４】
前記所定の条件が、以下のいずれか、すなわち、
−一定の反復回数に達したこと、
−前記スパース信号ベクトル内のすべての原シンボルの回復に成功したこと、
−
【数４９】
0005693750.tif 000156
、ここで、
【数５０】
0005693750.tif 000157
および
【数５１】
0005693750.tif 000158
は、１つの反復の前後の
【数５２】
0005693750.tif 000159
を表すこと
を含む、請求項１２に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、圧縮センシング（ｃｏｍｐｒｅｓｓｉｖｅ  ｓｅｎｓｉｎｇ）技術に関する。
【背景技術】
【０００２】
圧縮センシング（ＣＳ）は、最近開発された技法である。自然信号および人工的信号の大部分がスパース性または準スパース性を有する事実を考えると、圧縮センシング技法は、圧縮イメージング、圧縮サンプリング、信号処理、データストリーム・コンピューティング、および組み合わせグループ検査（ｃｏｍｂｉｎａｔｏｒｉａｌ  ｇｒｏｕｐ  ｔｅｓｔｉｎｇ）など、多くの異なる分野において応用を見出すことができる。圧縮センシングの基本的アイデアは、長さＮのスパース信号ｘ（信号が非ゼロ要素よりもはるかに多くのゼロ要素を含む場合、その信号はスパースであると言われる）は、長さＭの線形測定値（ｌｉｎｅａｒ  ｍｅａｓｕｒｅｍｅｎｔ）ｙ＝Ａｘから正確に回復できるというものであり、ここで、Ａは、Ｍ×Ｎ測定行列（ｍｅａｓｕｒｅｍｅｎｔ  ｍａｔｒｉｘ）であり、Ｍ＜＜Ｎである。
【０００３】
再構成は、測定ベクトル（ｍｅａｓｕｒｅｍｅｎｔ  ｖｅｃｔｏｒ）を説明する‖ｘ‖０の最小化を通して実行することができる。この最小化問題はＮＰ困難であるので、準最適なアルゴリズムが研究された。計算量的に実現可能なスパース信号回復アルゴリズムの主要なクラスは、凸緩和（ｃｏｎｖｅｘ  ｒｅｌａｘａｔｉｏｎ）を含み、凸緩和は、ｐにはしばしば１が選択されるｌｐ最小化問題によってｌ０最小化問題を近似し、凸最適化（ｃｏｎｖｅｘ  ｏｐｔｉｍｉｚａｔｉｏｎ）、最大の品質改善をもたらす１つまたは複数の成分を連続的に識別することによって、スパース解（ｓｐａｒｓｅ  ｓｏｌｕｔｉｏｎ）を反復的に精緻化する、マッチング追跡（ｍａｔｃｈｉｎｇ  ｐｕｒｓｕｉｔ）、信号ベクトルのスパース性に好都合な事前分布を仮定し、観測結果を組み込むために最大事後推定器（ｍａｘｉｍｕｍ  ａ  ｐｏｓｔｅｒｉｏｒｉ  ｅｓｔｉｍａｔｏｒ）を使用する、ベイズ・フレームワーク（Ｂａｙｅｓｉａｎ  ｆｒａｍｅｗｏｒｋ）を使用して、この問題を解く。実用上、それらの性能は比較的良好であるが、それらは、連続的な値を有する信号に最も適している。例えば、白黒画像を処理する場合のような、デジタル値を有するスパース信号の場合、これらのアルゴリズムは、適切に利用したならば、回復精度を大きく向上させ得る、ソースのデジタル性を利用できないので、あまり満足できるものではない。
【０００４】
したがって、信号のデジタル性を十分に利用できる、新しい圧縮センシング技法が必要である。
【０００５】
加えて、ほとんどすべての応用例において、測定行列Ａは、スパースであること、すなわち、各列に非ゼロ成分よりもはるかに多くのゼロ成分を含むことが好ましい。スパースな測定行列の利点として、符号化と復号の両方において計算複雑度が低いこと、信号を漸進的に更新することが容易であること、およびストレージ要件が低いことなどがある。多大な研究が、スパースな測定行列を用いるＣＳのために行われてきたが、それらのほとんどは、線形復号複雑度と性能限界とを同時に達成するに至っていない。既存のアルゴリズムの典型的な例は、マッチング追跡および凸最適化を含む。マッチング追跡タイプのアルゴリズムは、線形回復複雑度とともに、スケッチ長（ｓｋｅｔｃｈ  ｌｅｎｇｔｈ）の下限を漸近的に達成することができる。しかし、数値結果は、このタイプのアルゴリズムにおいて必要とされる経験的なスケッチ長は、常に漸近的限界よりもはるかに高いことを示した。他方、凸最適化タイプのアルゴリズムは、漸近的にも経験的にも、スケッチ長の下限を達成することができ、これは、実用上、測定値数に関して有利であることを示している。例えば、非ゼロ要素の数がＫ＝５０であり、信号長がＮ＝２００００である場合、マッチング追跡は、約２０００個の測定値を必要とするが、凸最適化は、約４５０個の測定値を必要とするにすぎないことが示された。凸最適化タイプのアルゴリズムの１つの主要な不都合は、回復複雑度がより高いことであり、信号長をＮとすると、多項式次数はＯ（Ｎ３）のようになる。
【０００６】
したがって、スパースな測定行列を用いて線形復号複雑度とスケッチ長の下限とを経験的に同時に達成できる、新しい圧縮センシング技法が必要である。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Ｒ．Ｇｒｉｂｏｎｖａｌ、Ｍ．Ｎｉｅｌｓｅｎ、「Ｈｉｇｈｌｙ  ｓｐａｒｓｅ  ｒｅｐｒｅｓｅｎｔａｔｉｏｎｓ  ｆｒｏｍ  ｄｉｃｔｉｏｎａｒｉｅｓ  ａｒｅ  ｕｎｉｑｕｅ  ａｎｄ  ｉｎｄｅｐｅｎｄｅｎｔ  ｏｆ  ｔｈｅ  ｓｐａｒｓｅｎｅｓｓ  ｍｅａｓｕｒｅ」、Ａａｌｂｏｒｇ  Ｕｎｉｖ．、Ａａｌｂｏｒｇ、Ｄｅｎｍａｒｋ、Ｔｅｃｈ．  Ｒｅｐ．、２００３年１０月
【非特許文献２】Ｊ．Ａ．Ｔｒｏｐｐ、「Ｊｕｓｔ  ｒｅｌａｘ：  Ｃｏｎｖｅｘ  ｐｒｏｇｒａｍｍｉｎｇ  ｍｅｔｈｏｄｓ  ｆｏｒ  ｉｄｅｎｔｉｆｙｉｎｇ  ｓｐａｒｓｅ  ｓｉｇｎａｌｓ  ｉｎ  ｎｏｉｓｅ」、ＩＥＥＥ  Ｔｒａｎｓ．Ｉｎｆ．Ｔｈｅｏｒｙ、ｖｏｌ．５２、ｎｏ．３、１０３０〜１０５１頁、２００６年３月
【非特許文献３】Ｓ．Ｊｉ、Ｙ．Ｘｕｅ、Ｌ．Ｃａｒｉｎ、「Ｂａｙｅｓｉａｎ  ｃｏｍｐｒｅｓｓｉｖｅ  ｓｅｎｓｉｎｇ」、ＩＥＥＥ  Ｔｒａｎｓ．  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇ、ｖｏｌ．５６、ｎｏ．６、２３４６〜２３５６頁、２００８年６月
【非特許文献４】Ｍ．Ｅ．Ｔｉｐｐｉｎｇ、「Ｓｐａｒｓｅ  Ｂａｙｅｓｉａｎ  ｌｅａｒｎｉｎｇ  ａｎｄ  ｔｈｅ  ｒｅｌｅｖａｎｃｅ  ｖｅｃｔｏｒ  ｍａｃｈｉｎｅ」、Ｊｏｕｒｎａｌ  ｏｆ  Ｍａｃｈｉｎｅ  Ｌｅａｒｎｉｎｇ  Ｒｅｓｅａｒｃｈ、ｖｏｌ．１、２１１〜２４４頁、２００１年９月
【非特許文献５】Ｍ．Ｊ．Ｗａｉｎｗｒｉｇｈｔ、「Ｓｈａｒｐ  ｔｈｒｅｓｈｏｌｄｓ  ｆｏｒ  ｈｉｇｈ−ｄｉｍｅｎｓｉｏｎａｌ  ａｎｄ  ｎｏｉｓｙ  ｓｐａｒｓｉｔｙ  ｒｅｃｏｖｅｒｙ  ｕｓｉｎｇ  １１−ｃｏｎｓｔｒａｉｎｅｄ  ｑｕａｄｒａｔｉｃ  ｐｒｏｇｒａｍｍｉｎｇ  （Ｌａｓｓｏ）」、ＩＥＥＥ  Ｔｒａｎｓ，  ｏｎ  Ｉｎｆｏｒｍ．  Ｔｈｅｏｒｙ、ｖｏｌ．５５、２１８３〜２２０２頁、２００９年５月
【非特許文献６】Ｒ．Ｔｉｂｓｈｉｒａｎｉ、「Ｒｅｇｒｅｓｓｉｏｎ  ｓｈｒｉｎｋａｇｅ  ａｎｄ  ｓｅｌｅｃｔｉｏｎ  ｖｉａ  ｔｈｅ  ｌａｓｓｏ」、Ｊｏｕｒｎａｌ  ｏｆ  ｔｈｅ  Ｒｏｙａｌ  Ｓｔａｔｉｓｔｉｃａｌ  Ｓｏｃｉｅｔｙ、Ｓｅｒｉｅｓ  Ｂ、２６７〜２８８頁、１９９６年
【発明の概要】
【課題を解決するための手段】
【０００８】
上述の２つの問題により良く対処するため、２つの技術的ソリューションが提供され、一方は、スパース信号のデジタル性を十分に利用できる、新しい圧縮センシング技法を提供することであり、他方は、スパースな測定行列を用いて線形復号複雑度とスケッチ長の下限とを経験的に同時に達成できる、新しい圧縮センシング技法を提供することである。
【０００９】
それらに基づいて、本発明の第１の態様では、デジタル・スパース信号を処理するための方法が提供される。方法は、長さＭの測定ベクトルｙを獲得するために、Ｍ×Ｎ測定行列Ａを用いて、長さＮのスパース信号ベクトルｘ＝｛ｘｉ｝に対して線形測定（ｌｉｎｅａｒ  ｍｅａｓｕｒｅｍｅｎｔ）を実行するステップであって、測定行列Ａが、
【００１０】
【数１】
0005693750.tif 000002
によって表される、ステップを含み、
ここで、ｄ＝１〜Ｄである、ΑｄΠｄは、測定行列Ａの部分行列であり、Πｄは、Ｎ×Ｎランダム置換行列（ｒａｎｄｏｍ  ｐｅｒｍｕｔａｔｉｏｎ  ｍａｔｒｉｘ）であり、Αｄは、
【００１１】
【数２】
0005693750.tif 000003
によって表されるＪ×Ｎ行列であり、
ここで、Ｍ＜＜Ｎ、Ｊ×Ｌ＝Ｎであり、スパース信号ベクトルｘ内の各成分ｘｉは、有限集合Ｑ＝｛Ｘ０＝０，Ｘ１，．．．，ＸＱ−１｝から取られ、ｑ＝１〜Ｑ−１の場合、Ｘｑはゼロ以外の数であり、Ｑは集合のサイズであり、同じ置換行列から生成された測定シンボルは、１つの次元と呼ばれ、Ｄは、総次元数である。
【００１２】
有利には、方法は、Ｄ個の次元に対してそれぞれ最尤検出を実行するために、Ｄ個の最尤検出器を使用するステップであって、第ｄの最尤検出器が、第ｄの次元に対して最尤検出を実行するために使用される、ステップと、所定の条件が満たされるまで、上記のステップを複数回反復して繰り返すステップと、最後の反復における第Ｄの最尤検出器の出力に基づいて、スパース信号ベクトル内の原シンボルを推定するステップとをさらに含むことができる。
【００１３】
本発明の第１の態様における測定行列Ａは、各次元におけるシンプルな最尤検出を可能にし、この最尤検出は、スパース信号のデジタル性を十分に利用し、次元ごとに計算量的に実現可能な局所最適な検出を提供する。測定行列の多次元構造は、準大域最適な推定結果を取得するために、次元間での反復的な情報交換を可能にする。
【００１４】
さらに、本発明の第１の態様における測定行列Ａは、スパースであり、すなわち、各列に非ゼロ成分よりもはるかに多くのゼロ成分を含む。測定行列のスパース性は、符号化と回復の両方において計算複雑度が低いこと、信号を漸進的に更新することが容易であること、およびストレージ要件が低いことなど、いくつかの魅力的な特性を有する。これらの利点は、本発明の第１の態様における技術的ソリューションを、スパースなデジタル信号を用いる圧縮センシングに対する有望で実用的なソリューションにする。
【００１５】
本発明の第２の態様では、アナログ・スパース信号を処理するための方法が提供される。方法は、長さＭの測定ベクトルｙを獲得するために、Ｍ×Ｎ測定行列Ａを用いて、長さＮのＫスパース信号ベクトルｘに対して線形測定を実行するステップであって、測定行列Ａが、
【００１６】
【数３】
0005693750.tif 000004
によって表される、ステップを含み、
ここで、ｄ＝１〜Ｄである、ΑｄΠｄは、測定行列Ａの部分行列であり、Πｄは、Ｎ×Ｎランダム置換行列であり、Αｄは、
【００１７】
【数４】
0005693750.tif 000005
によって表されるＪ×Ｎ行列であり、
ここで、Ｋ＜＜Ｎ、Ｍ＜＜Ｎ、Ｊ×Ｌ＝Ｎであり、スパース信号ベクトルｘは、ｘ＝｛ｘｉ｝∈ＲＮであり、同じ置換行列から生成された測定シンボルは、１つの次元と呼ばれ、Ｄは、総次元数である。
【００１８】
有利には、方法は、
ｉ．ｄ＝１〜Ｄ、ｊ＝１〜Ｊである、
【００１９】
【数５】
0005693750.tif 000006
内の各要素
【００２０】
【数６】
0005693750.tif 000007
について、
【００２１】
【数７】
0005693750.tif 000008
が０に等しいかどうかを判断するステップであって、
【００２２】
【数８】
0005693750.tif 000009
が、
【００２３】
【数９】
0005693750.tif 000010
と初期化され、
【００２４】
【数１０】
0005693750.tif 000011
が、
【００２５】
【数１１】
0005693750.tif 000012
の第ｄの次元内の第ｊの要素である、ステップと、
ｉｉ．
【００２６】
【数１２】
0005693750.tif 000013
が０に等しい場合、ｌ＝１〜Ｌとして、
【００２７】
【数１３】
0005693750.tif 000014
と設定するステップであって、ここで、Πｄ（ｉ）は、第ｄの置換結果におけるｘｉのインデックスであり、
【００２８】
【数１４】
0005693750.tif 000015
は、Πｄ（ｉ）の逆操作である、ステップと
をさらに含むことができ、
方法は、
ｕ．ｉ＝１〜Ｎである、スパース信号ベクトルｘ内の各原シンボルｘｉについて、以下の式
【００２９】
【数１５】
0005693750.tif 000016
が満たされるかどうかを判断するステップと、
ｖ．上記の式が（ｄｍ，ｄｎ）のペアについて満たされる場合、
【００３０】
【数１６】
0005693750.tif 000017
と設定するステップであって、ここで、
【００３１】
【数１７】
0005693750.tif 000018
および
【００３２】
【数１８】
0005693750.tif 000019
である、ステップと
をさらに含み、
上記のステップの後、方法は、
ｐ．回復されたスパース信号を、以下の式
【００３３】
【数１９】
0005693750.tif 000020
によって、測定ベクトルｙから減算することによって、
【００３４】
【数２０】
0005693750.tif 000021
を更新するステップであって、
ここで、
【００３５】
【数２１】
0005693750.tif 000022
は、未回復シンボルが０に設定された、回復されたスパース信号ベクトルを表す、ステップと、
ｑ．所定の条件が満たされるまで、上記のステップを複数回反復して繰り返すステップと
をさらに含む。
【００３６】
本発明の第２の態様における測定行列Ａの特殊な構造は、後で説明するような、測定シンボルのいくつかの興味深い特徴をもたらし、各反復における非常にシンプルな回復アルゴリズムを設計するために、その特徴を利用することができる。原信号を段階的に回復するために、反復プロセスが使用され、回復がより容易なシンボルから開始し、他のシンボルの回復が容易になるように、すでに回復されたシンボルの寄与を除去していく。そのような検出および除去操作を繰り返すことによって、準大域最適な解を獲得することができる。必要とされる複雑度は、原信号長Ｎにつれて線形に増加するにすぎない。多次元構造とランダム置換行列は、各測定値が、すべての原シンボルに対する何らかの有益な情報を（直接的または間接的に）統計的に提供することを保証し、この情報は、提案する技法の良好な性能にとって極めて重要である。
【００３７】
さらに、本発明の第２の態様における技術的ソリューションは、経験的なスケッチ長の下限と線形複雑度とを同時に達成することができる。良好な経験的性能と低い複雑度は、本発明の第２の態様における技術的ソリューションを、スパースな測定行列を用いる圧縮センシングに対する良好で実用的な代替ソリューションにする。
【００３８】
加えて、本発明の一実施形態によれば、スパース信号を測定および回復するための装置が提供され、装置は、長さＭの測定ベクトルｙを獲得するために、Ｍ×Ｎ測定行列Ａを用いて、長さＮのスパース信号ベクトルｘ＝｛ｘｉ｝に対して線形測定を実行するための測定手段であって、測定行列Ａが、
【００３９】
【数２２】
0005693750.tif 000023
によって表され、
ここで、ｄ＝１〜Ｄである、ΑｄΠｄは、測定行列Ａの部分行列であり、Πｄは、Ｎ×Ｎランダム置換行列であり、Αｄは、
【００４０】
【数２３】
0005693750.tif 000024
によって表されるＪ×Ｎ行列であり、
ここで、Ｍ＜＜Ｎ、Ｊ×Ｌ＝Ｎであり、同じ置換行列から生成された測定シンボルは、１つの次元と呼ばれ、Ｄは、総次元数である、測定手段と、
長さＮのスパース信号ベクトルｘ＝｛ｘｉ｝を長さＭの測定ベクトルｙから回復するための回復手段と
を備える。
【００４１】
本発明が、添付の図面を参照しながら、例によって、さらに詳細に説明される。
【図面の簡単な説明】
【００４２】
【図１】一実施形態による、デジタル・スパース信号の処理についてのフローチャートである。
【図２】図１において使用される反復アルゴリズムの原理を示す図である。
【図３ａ】ｐ１＝０．１を用いた場合の、図１の実施形態と２つの従来技法の間の速度−歪み性能（ｒａｔｅ−ｄｉｓｔｏｒｔｉｏｎ  ｐｅｒｆｏｒｍａｎｃｅ）の比較を示す図である。
【図３ｂ】ｐ１＝０．０５を用いた場合の、図１の実施形態と２つの従来技法の間の速度−歪み性能の比較を示す図である。
【図４】別の実施形態による、アナログ・スパース信号の処理についてのフローチャートである。
【図５】図４の実施形態の、測定値数ＭとＫｌｏｇ２（Ｎ／Ｋ）の間の関係を示す図である。
【図６ａ】ｐ１＝０．１を用いた場合の、図４の実施形態の、回復失敗確率とαの間の関係を示す図である。
【図６ｂ】ｐ１＝０．０５を用いた場合の、図４の実施形態の、回復失敗確率とαの間の関係を示す図である。
【発明を実施するための形態】
【００４３】
上記の図面全体において、同様の参照番号は、同様の、類似の、または対応する特徴または機能を指示することが理解されよう。
【００４４】
これ以降本明細書において、本発明の上記の第１の態様の技術的ソリューションと、本発明の上記の第２の態様の技術的ソリューションが、それぞれ非常に詳細に説明される。
【００４５】
図１は、一実施形態による、デジタル・スパース信号の処理についてのフローチャートを示している。
【００４６】
ステップＳ１１において、長さＭの測定ベクトルｙを獲得するために、Ｍ×Ｎ測定行列Ａを用いて、長さＮのデジタル・スパース信号ベクトルｘに対して線形測定（すなわち符号化）が実行され、ここで、Ｍ＜＜Ｎである。
【００４７】
独立した一様分布する（ｉ．ｉ．ｄ：ｉｎｄｅｐｅｎｄｅｎｔ  ａｎｄ  ｉｄｅｎｔｉｃａｌｌｙ  ｄｉｓｔｒｉｂｕｔｅｄ）成分を有するデジタル・スパース信号ベクトルｘ＝｛ｘｉ｝を考える。スパース信号ベクトルｘ内の各成分ｘｉの値は、有限集合Ｑ＝｛Ｘ０＝０，Ｘ１，．．．，ＸＱ−１｝から取られ、ｑ＝１〜Ｑ−１の場合、Ｘｑはゼロ以外の数字であり、Ｑは集合のサイズである。各成分ｘｉは、「０」である確率がｐ０であり、Ｘｑである確率がｐｑ（ｑ＝１〜Ｑ−１）であると仮定する。ｘはスパースであるので、
【００４８】
【数２４】
0005693750.tif 000025
である。
【００４９】
圧縮センシングの理論に基づいて、ｘは、以下のような測定ベクトルｙから回復することができ、
ｙ＝Ａｘ＋ｎ    （１）
ここで、ｎは、ゼロ平均を有し、Ｅ（｜ｎ｜２）≦Ｍσ２である、長さＭの雑音ベクトルである。
【００５０】
この実施形態では、測定行列Ａは、以下のように設計され、
【００５１】
【数２５】
0005693750.tif 000026
ここで、ＡｄΠｄ（ｄ＝１〜Ｄ）は、測定行列Ａの部分行列であり、
Πｄは、Ｎ×Ｎランダム置換行列であり、
Ａｄは、以下のように設計されるＪ×Ｎ行列であり、
【００５２】
【数２６】
0005693750.tif 000027
ここで、Ｊ×Ｌ＝Ｎであり、同じ置換行列から生成される測定シンボルは、１つの次元と呼ばれ、Ｄは、総次元数である。置換行列｛Πｄ｝は、Ｄ個の次元ごとに独立かつランダムに生成される。｛Ａｄ｝内の非ゼロ成分は、ガウス確率変数である。
【００５３】
符号化プロセスは、以下のように実施することができる。デジタル・スパース信号ベクトルｘ内の原シンボルは、Ｄ回、独立して置換される。各回の置換結果は、Ｊ＝Ｎ／Ｌ個のグループに分割され、各グループは、Ｌ個のシンボルを含む。第ｄの置換結果の第ｊのグループ内のシンボルは、Ａｄの第ｊ行内の対応する非ゼロ成分によって重み付けされた後、線形に重ね合わされて、この次元における第ｊの測定シンボルを生成する。全測定値の数Ｍは、グループ長Ｌ、次元数Ｄ、および信号長Ｎによって、Ｍ＝ＮＤ／Ｌのように決定される。
【００５４】
符号化の後、測定シンボルをデジタル化するために、量子化プロセスが適用される。量子化誤差は、式（１）の雑音ベクトルｎによって表される。Ｓが、量子化レベルの数を表すとし、ｐｑｕａｎ（ｓ）が、測定シンボルがレベルＳに量子化される確率を表すとする。その場合、１つの量子化された測定値を表すのに必要なビットの数は、
【００５５】
【数２７】
0005693750.tif 000028
である。
【００５６】
したがって、ｘを表すのに必要なビットの総数は、Ｂ＝ｂＭ＝ｂＮＤ／Ｌであり、原シンボル当たり必要なビットの平均数は、
【００５７】
【数２８】
0005693750.tif 000029
である。
【００５８】
原シンボル当たりの平均ビット数は、Ｄ、Ｌ、およびＳの選択を介して調整することができる。
【００５９】
式（３）における｛Ａｄ｝の構造は、各次元において、Ｌ個のシンボルからなる各グループに対して、最尤検出（ＭＬ）を使用することを可能にする。Ｌに小さな値を選択することによって、ＭＬ検出の計算複雑度を制御することができる。ＭＬ検出は、原信号のデジタル性を十分に利用することができ、各次元ごとに、局所最適解を提供することができる。多次元構造は、準大域最適推定を達成するために、次元間での反復的な情報交換を可能にする。異なる次元における独立したランダム置換行列は、１つの次元における異なる測定値に寄与するシンボルは一緒にグループ化でき、他の次元における同じ測定値にも寄与できるので、統計的に、各測定値が、デジタル・スパース信号ベクトルｘ内のすべてのシンボルに対する何らかの有益な情報を（直接的または間接的に）提供できることを保証する。これは、１つの測定値によって提供される、それに関連するＬ個のシンボルに対する情報は、これらのＬ個のシンボルが他の次元における他のシンボルとグループ化される場合、他のシンボルの検出に役立ち得ることを意味する。そのような特性は、提案する技法の耐雑音能力を大きく向上させるために、反復的な回復アルゴリズムにおいて十分に利用される。
【００６０】
それに基づいて、ステップＳ１２において、Ｄ個の次元に対してそれぞれ最尤検出を実行するために、Ｄ個の最尤検出器が使用される。すなわち、各最尤検出器は、図２に示されるように、１つの次元の検出を担当する。図２は、反復的なアルゴリズムの原理を示しており、「ＤＥＴ−ｄ」は、第ｄの次元のローカル検出器であり、「Ｔ」は、１つの反復の遅延を表し、「／」は、除法演算を表す。
【００６１】
各ローカル検出器内で、Ｌ個のシンボルからなる各グループに対して、それらの雑音測定シンボルと事前情報とに基づいて、ＭＬ検出が実行される。各検出器の出力は、デジタル・スパース信号ベクトルｘ内の原シンボルの事後情報であり、それは、次の反復において、他の次元における局所検出を精緻化するために使用される。
【００６２】
図２に含まれる変数は、以下のように定義される。
【００６３】
【数２９】
0005693750.tif 000030
：第ｄの次元において、ｘｉがＸｑ（ｑ＝０〜Ｑ−１）である事前確率（ａ  ｐｒｉｏｒｉ  ｐｒｏｂａｂｉｌｉｔｙ）。
ｐ（ｄ）（ｘｉ＝Ｘｑ）：第ｄの次元において、ｘｉがＸｑ（ｑ＝０〜Ｑ−１）である事後確率（ａ  ｐｏｓｔｅｒｉｏｒｉ  ｐｒｏｂａｂｉｌｉｔｙ）。
ｅ（ｄ）（ｘｉ＝Ｘｑ）：第ｄの次元において、ｘｉがＸｑ（ｑ＝０〜Ｑ−１）である外部確率（ｅｘｔｒｉｎｓｉｃ  ｐｒｏｂａｂｉｌｉｔｙ）。
【００６４】
事前確率は、第１の反復において、ｉ＝１〜Ｎ、ｑ＝０〜Ｑ−１に対して、
【００６５】
【数３０】
0005693750.tif 000031
のように初期化され、外部確率は、第１の反復において、∀ｄに対して、ｅ（ｄ）（ｘｉ＝Ｘｑ）＝１のように初期化される。
【００６６】
【数３１】
0005693750.tif 000032
によって表される、第ｄの次元における特定の測定値ｊについて考える。
【００６７】
【数３２】
0005693750.tif 000033
に寄与するＬ個の原シンボルのインデックスを
【００６８】
【数３３】
0005693750.tif 000034
とする。
【００６９】
【数３４】
0005693750.tif 000035
の値は、置換行列Πｄによって決定される。これらＬ個のシンボルの事後確率は、ＭＬ検出を使用して、
【００７０】
【数３５】
0005693750.tif 000036
のように計算される。
【００７１】
式（６）における総和は、第ｌの要素がＸｑに固定された、すべての可能なベクトルｃ∈ＱＬを対象とする。外部確率は、事後確率から事前確率を抽出することによって計算される。
【００７２】
【数３６】
0005693750.tif 000037
【００７３】
第ｄの次元において生成された事後確率は、第（ｍｏｄ（ｄ，Ｄ）＋１）の次元における事前確率を、
【００７４】
【数３７】
0005693750.tif 000038
のように更新するために使用される。
【００７５】
ｅ（ｍｏｄ（ｄ，Ｄ）＋１）（ｘｉ＝Ｘｑ）は、先行する反復における第（ｍｏｄ（ｄ，Ｄ）＋１）の次元において生成されるので、循環して再び第（ｍｏｄ（ｄ，Ｄ）＋１）の次元に戻ることがないようにすべきであり、これは反復的な検出の基本規則であることに留意されたい。これは、式（８）における除法演算によって実現される。
【００７６】
その後、ステップＳ１３において、上述の手順を、所定の条件が満たされるまで、複数回反復して繰り返す。
【００７７】
所定の条件は、例えば、以下のいずれかを含むことができる。
−一定の反復回数に達した。
−２つの連続する反復において第Ｄの最尤検出器において生成された事後確率の間の差が事前定義された閾値を下回った。
【００７８】
最後に、ステップＳ１４において、デジタル・スパース信号ベクトルｘ内の原シンボル｛ｘｉ｝が、最後の反復における第Ｄの最尤検出器の出力に基づいて推定される。
【００７９】
例えば、原シンボル｛ｘｉ｝に対して、以下のような硬判定（ｈａｒｄ  ｄｅｃｉｓｉｏｎ）が行われる。
【００８０】
【数３８】
0005693750.tif 000039
ここで、
【００８１】
【数３９】
0005693750.tif 000040
である。
【００８２】
この実施形態における上で提案した反復アルゴリズムの複雑度は、Ｏ（ＮＤＱＬ／Ｌ）であり、これは、ＬがＮよりもはるかに小さく、Ｎとともに大きくならないので、最適なソリューションの複雑度Ｏ（ＱＮ）よりもはるかに低い。Ｄが一定である場合、Ｌが小さくなるほど、測定値数Ｍは多くなることに留意されたい。そのため、ＤとＬの値を調整することによって、計算複雑度と測定値数の間の異なるトレードオフを達成することができる。
【００８３】
以下の説明では、上で提案した技術的ソリューションの性能を、数値結果を使用して説明する。ｘｉ∈｛０，１｝である、デジタル・スパース信号ベクトルｘ内の２進原信号を考える。ｘの成分は、「０」（「１」）である確率がｐ０（ｐ１）であり、ｐ０＞＞ｐ１である、独立した一様分布する変数である。ゼロ平均および単位分散を有する、独立した一様分布するガウス確率変数である、非ゼロ成分を有する、測定行列Ａが、式（２）および（３）に従って生成される。測定行列Ａは、各行が単位ノルムを有するように正規化される。量子化レベルは、Ｓ＝５に固定され、以下の量子化規則が用いられ、
【００８４】
【数４０】
0005693750.tif 000041
ここで、Ｑｕａｎ（ｘ）は、量子化後のｘの値を表す。
【００８５】
デジタル・スパース信号ベクトルｘを用いる場合、（量子化前の）式（２）および（３）において定義された測定行列Ａを使用して生成される線形測定シンボルは、「０」である確率が大きいことに留意されたい。ゼロ測定シンボルが出現した場合、それに関連するＬ個の原シンボルはすべてゼロであると高い精度で結論を下すことができ、これは、反復的な回復アルゴリズムにおける他の原シンボルの検出に非常に役立つ。したがって、「０」を他の値から区別するために、式（２０）における「０」のために特定の量子化レベルが使用される。確率｛Ｐｑｕａｎ（ｓ），ｓ＝１〜５｝を獲得するためにモンテカルロ・シミュレーションを使用し、式（５）に従って、原シンボル当たり必要なビットの平均数ηを計算する。
【００８６】
図３ａおよび図３ｂは、上で提案した技術的ソリューションと、ランダム・ガウス・センシング行列、ラッソ・アルゴリズム（Ｌａｓｓｏ  ａｌｇｏｒｉｔｈｍ）、およびベイズ・フレームワークにそれぞれ基づいた、２つの従来技法との間の速度−歪み性能の比較を示している。可逆回復の場合に原シンボル当たり必要なビットの最小数も、参考のために示されている。
【００８７】
ここでは、ｐ１＝０．１および０．０５に設定し、反復回数は５に固定する。確率｛Ｐｑｕａｎ（ｓ）｝が、表１に挙げられている。
【００８８】
【表１】
0005693750.tif 000042
【００８９】
表１から、原シンボル当たり必要なビットの数ηを計算することができる。０．１４から１までのηの異なる値を獲得するために、Ｄを１から４まで、Ｌを１０から１２までの間で調整する。ξによって表される歪みは、以下のように測定され、
【００９０】
【数４１】
0005693750.tif 000043
それは、Ｎによって正規化された
【００９１】
【数４２】
0005693750.tif 000044
内の不正確な成分の平均数に等しい。
【００９２】
参考のため、エントロピ符号化を介する可逆圧縮の場合に原シンボル当たり必要なビットの最小数が、図３に示されている。２つの従来手法の速度−歪み性能も含まれており、２つの従来手法は、ランダム・ガウス・センシング行列に基づき、信号回復のために、凸緩和（詳細については、［Ｒ．Ｇｒｉｂｏｎｖａｌ、Ｍ．Ｎｉｅｌｓｅｎ、「Ｈｉｇｈｌｙ  ｓｐａｒｓｅ  ｒｅｐｒｅｓｅｎｔａｔｉｏｎｓ  ｆｒｏｍ  ｄｉｃｔｉｏｎａｒｉｅｓ  ａｒｅ  ｕｎｉｑｕｅ  ａｎｄ  ｉｎｄｅｐｅｎｄｅｎｔ  ｏｆ  ｔｈｅ  ｓｐａｒｓｅｎｅｓｓ  ｍｅａｓｕｒｅ」、Ａａｌｂｏｒｇ  Ｕｎｉｖ．、Ａａｌｂｏｒｇ、Ｄｅｎｍａｒｋ、Ｔｅｃｈ．  Ｒｅｐ．、２００３年１０月］および［Ｊ．Ａ．Ｔｒｏｐｐ、「Ｊｕｓｔ  ｒｅｌａｘ：  Ｃｏｎｖｅｘ  ｐｒｏｇｒａｍｍｉｎｇ  ｍｅｔｈｏｄｓ  ｆｏｒ  ｉｄｅｎｔｉｆｙｉｎｇ  ｓｐａｒｓｅ  ｓｉｇｎａｌｓ  ｉｎ  ｎｏｉｓｅ」、ＩＥＥＥ  Ｔｒａｎｓ．Ｉｎｆ．Ｔｈｅｏｒｙ、ｖｏｌ．５２、ｎｏ．３、１０３０〜１０５１頁、２００６年３月］を参照されたい）と、ベイズ・フレームワーク（詳細については、［Ｓ．Ｊｉ、Ｙ．Ｘｕｅ、Ｌ．Ｃａｒｉｎ、「Ｂａｙｅｓｉａｎ  ｃｏｍｐｒｅｓｓｉｖｅ  ｓｅｎｓｉｎｇ」、ＩＥＥＥ  Ｔｒａｎｓ．  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇ、ｖｏｌ．５６、ｎｏ．６、２３４６〜２３５６頁、２００８年６月］および［Ｍ．Ｅ．Ｔｉｐｐｉｎｇ、「Ｓｐａｒｓｅ  Ｂａｙｅｓｉａｎ  ｌｅａｒｎｉｎｇ  ａｎｄ  ｔｈｅ  ｒｅｌｅｖａｎｃｅ  ｖｅｃｔｏｒ  ｍａｃｈｉｎｅ」、Ｊｏｕｒｎａｌ  ｏｆ  Ｍａｃｈｉｎｅ  Ｌｅａｒｎｉｎｇ  Ｒｅｓｅａｒｃｈ、ｖｏｌ．１、２１１〜２４４頁、２００１年９月］を参照されたい）とをそれぞれ利用する。凸緩和の場合、ラッソ・アルゴリズム（詳細については、［Ｍ．Ｊ．Ｗａｉｎｗｒｉｇｈｔ、「Ｓｈａｒｐ  ｔｈｒｅｓｈｏｌｄｓ  ｆｏｒ  ｈｉｇｈ−ｄｉｍｅｎｓｉｏｎａｌ  ａｎｄ  ｎｏｉｓｙ  ｓｐａｒｓｉｔｙ  ｒｅｃｏｖｅｒｙ  ｕｓｉｎｇ  １１−ｃｏｎｓｔｒａｉｎｅｄ  ｑｕａｄｒａｔｉｃ  ｐｒｏｇｒａｍｍｉｎｇ  （Ｌａｓｓｏ）」、ＩＥＥＥ  Ｔｒａｎｓ，  ｏｎ  Ｉｎｆｏｒｍ．  Ｔｈｅｏｒｙ、ｖｏｌ．５５、２１８３〜２２０２頁、２００９年５月］および［Ｒ．Ｔｉｂｓｈｉｒａｎｉ、「Ｒｅｇｒｅｓｓｉｏｎ  ｓｈｒｉｎｋａｇｅ  ａｎｄ  ｓｅｌｅｃｔｉｏｎ  ｖｉａ  ｔｈｅ  ｌａｓｓｏ」、Ｊｏｕｒｎａｌ  ｏｆ  ｔｈｅ  Ｒｏｙａｌ  Ｓｔａｔｉｓｔｉｃａｌ  Ｓｏｃｉｅｔｙ、Ｓｅｒｉｅｓ  Ｂ、２６７〜２８８頁、１９９６年］を参照されたい）を使用する。ベイズ・フレームワークに基づいたアルゴリズムの場合、論文（Ｓ．Ｊｉ、Ｙ．Ｘｕｅ、Ｌ．Ｃａｒｉｎ、「Ｂａｙｅｓｉａｎ  ｃｏｍｐｒｅｓｓｉｖｅ  ｓｅｎｓｉｎｇ」、ＩＥＥＥ  Ｔｒａｎｓ．  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇ、ｖｏｌ．５６，  ｎｏ．６、２３４６〜２３５６頁、２００８年６月）に紹介された技法が使用される。このケースでは、各測定値が「０」になる可能性は非常に低いので、「０」専用の量子化レベルを除去したことを除いて、従来手法はどちらも、式（１１）と同様の量子化規則を使用する。従来手法の場合の確率｛ｐｑｕａｎ（ｓ），ｓ＝１〜５｝も、表１に挙げられている。図３から、提案した技法は、ランダム・センシング行列と凸緩和／ベイズ・フレームワークとに基づいた従来手法よりもはるかに良好な速度−歪み性能を達成できることが観測される。
【００９３】
図４は、別の実施形態による、アナログ・スパース信号の処理についてのフローチャートを示している。
【００９４】
ステップＳ４１において、長さＭの測定ベクトルｙを獲得するために、Ｍ×Ｎ測定行列Ａを用いて、長さＮのＫスパース信号ベクトルｘに対して線形測定（すなわち符号化）が実行され、ここで、Ｋ＜＜Ｎ、Ｍ＜＜Ｎであり、Ｋスパース信号ベクトルは、ｘ＝｛ｘｉ｝∈ＲＮであり、測定ベクトルは、ｙ∈ＲＭである。
【００９５】
圧縮センシングの理論によれば、ｘは、以下のような測定ベクトルｙから回復することができる。
ｙ＝Ａｘ  （１３）
【００９６】
この実施形態では、測定行列Ａは、以下のように設計され、
【００９７】
【数４３】
0005693750.tif 000045
ここで、ＡｄΠｄ（ｄ＝１〜Ｄ）は、測定行列Ａの部分行列であり、Πｄは、Ｎ×Ｎランダム置換行列であり、Ａｄは、以下のように設計されるＪ×Ｎ行列であり、
【００９８】
【数４４】
0005693750.tif 000046
ここで、Ｊ×Ｌ＝Ｎであり、同じ置換行列から生成される測定シンボルは、１つの次元と呼ばれ、Ｄは、総次元数である。明らかに、このようにして生成された測定行列Ａは、スパースであり、列当たりＤ個の非ゼロ成分を有するにすぎない。
【００９９】
符号化操作は、以下のように実施することができる。デジタル・スパース信号ベクトルｘ内の原シンボルは、Ｄ回、独立して置換される。各回の置換結果は、Ｊ＝Ｎ／Ｌ個のグループに分割され、各グループは、Ｌ個のシンボルを含む。第ｄの置換結果の第ｊのグループ内のシンボルは、Ａｄの第ｊ行内の対応する非ゼロ成分によって重み付けされた後、線形に重ね合わされて、この次元における第ｊの測定を生成する。
【０１００】
【数４５】
0005693750.tif 000047
によって、第ｄの次元における第ｊの測定シンボルを表し、それは、
【０１０１】
【数４６】
0005693750.tif 000048
となり、
ここで、
【０１０２】
【数４７】
0005693750.tif 000049
は、ｘの第ｄの置換結果である。Πｄ（ｉ）を、第ｄの置換結果におけるｘｉのインデックスとし、
【０１０３】
【数４８】
0005693750.tif 000050
は、その逆操作であり、
【０１０４】
【数４９】
0005693750.tif 000051
となる。
【０１０５】
スパース信号ベクトルｘ内のどの原シンボルｘｉにも、１つの次元内から１つずつ、Ｄ個の測定値が関連付けられる。総測定値数（すなわちスケッチ長）Ｍは、グループ長Ｌ、次元数Ｄ、および原信号長Ｎによって、Ｍ＝ＮＤ／Ｌのように決定される。
【０１０６】
式（１６）から、測定行列Ａは、各列内にＤ個の非ゼロ要素を有するにすぎないことが分かる。ｘの非ゼロ要素だけが、符号化における加法および乗法演算に成立させることにも留意されたい。したがって、提案した技法の符号化複雑度は、ＤＫ個の乗算およびＤＫ個の加算についてのものである。
【０１０７】
式（１５）における｛Ａｄ｝のブロック対角構造と、Ｄ個の次元におけるランダム置換行列は、測定シンボルの以下の特徴をもたらし、それは、信号回復において非常に役立つ。説明に便利なように、測定シンボルの次数（ｄｅｇｒｅｅ）を、測定シンボルに関連付けられた非ゼロ原シンボルの数として定義する。（１６）から、各測定シンボル
【０１０８】
【数５０】
0005693750.tif 000052
は、Ｌ個の原シンボル
【０１０９】
【数５１】
0005693750.tif 000053
に関連付けられるにすぎないことが分かり、したがって、以下の２つの事態が、比較的大きな確率で発生することを検証することは容易である。
事態１：測定シンボルが次数０を有する。
事態２：非ゼロ原シンボルの場合、それに関連付けられた少なくとも２つの測定値が次数１を有する（Ｄ≧２を仮定する）。
【０１１０】
上記の２つの事態の確率は、以下のように計算することができる。ｐ１＝Ｋ／Ｎ、ｐ０＝１−ｐ１とする。ｐ１およびｐ０は、原シンボルが非ゼロおよびゼロである確率をそれぞれ表す。その場合、事態１および事態２の確率は、
【０１１１】
【数５２】
0005693750.tif 000054
および
【０１１２】
【数５３】
0005693750.tif 000055
のように近似的に計算することができる。
【０１１３】
Ｋ＜＜Ｎである場合、ＬおよびＤに適切な値を選択することによって、２つの確率を比較的大きくできることが容易に分かる。例えば、Ｋ＝１００、Ｎ＝１０００、Ｌ＝１０、Ｄ＝４である場合、Ｐｉｓｓｕｅ−１＝３４．８７％、Ｐｉｓｓｕｅ−２＝５０．２９％である。
【０１１４】
事態１の場合、測定シンボルは、ゼロである。測定シンボルが、２つ以上の非ゼロ原シンボルに関連付けられる場合、これらの非ゼロシンボルが、互いに完全に相殺し合う可能性は非常に低く（式（１６）を参照）、そのため、測定シンボルは、１に近い、非ゼロである確率を有することも留意されたい。したがって、ゼロの測定シンボルが現れた場合、それに関連付けられたすべての原シンボルはゼロであると推測することができる。
【０１１５】
事態２の場合、非ゼロ原シンボルの２つの次数１の測定値は、以下のような関係にある。非ゼロ原シンボルｘｉが、２つの次数１の測定値を次元ｄ１およびｄ２において有すると仮定する。ｍ＝１および２に対して、
【０１１６】
【数５４】
0005693750.tif 000056
および
【０１１７】
【数５５】
0005693750.tif 000057
とする。これら２つの次数１の測定値の値は、以下の関係を有する。
【０１１８】
【数５６】
0005693750.tif 000058
【０１１９】
明らかに、ｘｉの値は、式（２０）から計算することができる。
【０１２０】
事態１および２についての上述の説明に基づいて、次にステップＳ４２において、
【０１２１】
【数５７】
0005693750.tif 000059
内の各要素
【０１２２】
【数５８】
0005693750.tif 000060
（ｄ＝１〜Ｄ、ｊ＝１〜Ｊ）について、
【０１２３】
【数５９】
0005693750.tif 000061
が０に等しいかどうかを判断し、
【０１２４】
【数６０】
0005693750.tif 000062
が０に等しい場合、ｌ＝１〜Ｌとして、
【０１２５】
【数６１】
0005693750.tif 000063
と設定し、ここで、
【０１２６】
【数６２】
0005693750.tif 000064
は、
【０１２７】
【数６３】
0005693750.tif 000065
のように初期化され、
ｉ＝１〜Ｎである、スパース信号ベクトルｘ内の各原シンボルｘｉに対して、
以下の式が満たされるかどうかが判断され、
【０１２８】
【数６４】
0005693750.tif 000066
上記の式が（ｄｍ，ｄｎ）のペアについて満たされる場合、
【０１２９】
【数６５】
0005693750.tif 000067
と設定する。
【０１３０】
次にステップＳ４３において、回復されたスパース信号を、以下の式
【０１３１】
【数６６】
0005693750.tif 000068
によって、測定ベクトルｙから減算することによって、
【０１３２】
【数６７】
0005693750.tif 000069
が更新され、
ここで、
【０１３３】
【数６８】
0005693750.tif 000070
は、未回復のシンボルが０に設定された、回復されたスパース信号ベクトルを表す。
【０１３４】
そのような干渉除去操作は、２つの方法で、他のシンボルの回復に役立つ。第１に、測定シンボルに関連付けられた原シンボルが、１つを除いてすべて回復された場合、未回復の原シンボルだけを（干渉除去後に）測定値から直接的に推定することができる。第２に、非ゼロ原シンボルが、ｙから減算される場合、それに関連付けられた測定値の次数が、１だけ減らされる。これによって、事態１および２の新しいケースを
【０１３５】
【数６９】
0005693750.tif 000071
において導入することができるので、上記の２つの規則を再び適用して、
【０１３６】
【数７０】
0005693750.tif 000072
からより多くの原シンボルを再生成することができる。これが、再帰的にｘを回復するために、干渉除去とともに反復的なプロセスを使用する動機になる。
【０１３７】
次にステップＳ４４において、上述のステップＳ４２およびＳ４３が、所定の条件が満たされるまで、複数回反復して繰り返される。
【０１３８】
所定の条件は、例えば、以下のいずれかを含むことができる。
−一定の反復回数に達した。
−スパース信号ベクトル内のすべての原シンボルの回復に成功した。
−
【０１３９】
【数７１】
0005693750.tif 000073
、ここで、
【０１４０】
【数７２】
0005693750.tif 000074
および
【０１４１】
【数７３】
0005693750.tif 000075
は、１つの反復の前後の
【０１４２】
【数７４】
0005693750.tif 000076
を表す。
【０１４３】
この実施形態における上で提案した反復アルゴリズムの複雑度は、Ｏ（Ｎ）である。
【０１４４】
以下の説明では、上で提案した技術的ソリューションの性能が、数値結果を使用して説明される。非ゼロ要素としてガウス確率変数を有するスパース原信号ｘを考える。非ゼロ成分としてガウス確率変数を有する測定行列Ａが、式（１４）および（１５）に従って生成される。シミュレーションでは、ｐ１＝Ｋ／Ｎ＝０．１および０．０５に設定され、次元数はＤ＝４である。異なるスケッチ長Ｍが得られるように、グループ長Ｌが調整される。反復的な回復プロセスは、以下の３つの条件のいずれか１つが満たされた場合に終了する。ａ）Ｔ＝２０回の反復に達した、ｂ）すべての原シンボルの回復に成功した、ｃ）
【０１４５】
【数７５】
0005693750.tif 000077
、ここで、
【０１４６】
【数７６】
0005693750.tif 000078
および
【０１４７】
【数７７】
0005693750.tif 000079
は、１つの反復の前後の
【０１４８】
【数７８】
0005693750.tif 000080
の結果である。平均反復回数は、Ｍ／Ｎに応じて、Ｔａｖｅ＝６〜１０である。
【０１４９】
図５は、測定値数ＭとＫｌｏｇ２（Ｎ／Ｋ）の間の関係を示している。この図の目的は、提案した技法がスケッチ長の下限Ｏ（Ｋｌｏｇ２（Ｎ／Ｋ））を達成できることを示すことである。図５には、上で提案した技術的ソリューションの場合、必要とされる測定値の数Ｍが信号長Ｎとともに線形に増加することが示されている。ここで、Ｎを１０００から１００００までに設定し、回復失敗確率が高々０．０１であることを保証するようにＭを選択する。回復失敗は、
【０１５０】
【数７９】
0005693750.tif 000081
である場合に発生し、ここで、
【０１５１】
【数８０】
0005693750.tif 000082
は、最後の反復後の
【０１５２】
【数８１】
0005693750.tif 000083
を表すことに留意されたい。図５は、提案した技術的ソリューションが、αが約０．６〜０．８の非常に小さな値を取る場合に、α・Ｋｌｏｇ２（Ｎ／Ｋ）のスケッチ長下限を経験的に達成できることを明らかに示している。
【０１５３】
図６ａおよび図６ｂは、上で提案した技術的ソリューションの場合の、回復失敗確率とα（すなわちスケッチ長）の間の関係を示している。ここで、Ｎ＝４０００は、一定であり、αは、０．５〜１．２の間で変化する。比較のため、図６には、ｌ１マジック（ｌ１  ｍａｇｉｃ）とベイズ・フレームワークとに基づいた既存の回復アルゴリズムの場合の、回復失敗確率も示されている。見て分かるように、同じ回復精度を達成するのに、上で提案した技術的ソリューションは、ｌ１マジックおよびベイズ・フレームワークよりもはるかに少ない測定値しか必要としない。そのような良好なスケッチ長は、線形複雑度を有するように達成される。良好な経験的性能および線形回復複雑度は、提案する技法を、スパースな行列を用いる圧縮センシングに対する有望で魅力的なソリューションにする。
【０１５４】
上では、本発明の技術的ソリューションを方法の観点から説明したが、これ以降では、本発明の技術的ソリューションを装置の観点からさらに説明する。
【０１５５】
本発明の一実施形態によれば、スパース信号を測定および回復するための装置がさらに提供される。装置は、長さＭの測定ベクトルｙを獲得するために、Ｍ×Ｎ測定行列Ａを用いて、長さＮのスパース信号ベクトルｘ＝｛ｘｉ｝に対して線形測定を実行するための測定手段であって、測定行列Ａが、
【０１５６】
【数８２】
0005693750.tif 000084
によって表され、
ここで、ｄ＝１〜Ｄである、ＡｄΠｄ、測定行列Ａの部分行列であり、Πｄは、Ｎ×Ｎランダム置換行列であり、Ａｄは、
【０１５７】
【数８３】
0005693750.tif 000085
によって表されるＪ×Ｎ行列であり、
ここで、Ｍ＜＜Ｎ、Ｊ×Ｌ＝Ｎであり、同じ置換行列から生成される測定シンボルは、１つの次元と呼ばれ、Ｄは、総次元数である、測定手段と、
長さＮのスパース信号ベクトルｘ＝｛ｘｉ｝を長さＭの測定ベクトルｙから回復するための回復手段と
を備える。
【０１５８】
有利には、スパース信号がデジタル・スパース信号であり、スパース信号ベクトルｘ内の各成分ｘｉが有限集合Ｑ＝｛Ｘ０＝０，Ｘ１，．．．，ＸＱ−１｝から取られ、ｑ＝１〜Ｑ−１の場合のＸｑがゼロ以外の数字であり、Ｑが集合のサイズである場合、回復手段は、Ｄ個の次元に対して最尤検出をそれぞれ実行するためのＤ個の最尤検出器を含む検出手段であって、第ｄの最尤検出器が、第ｄの次元に対する最尤検出を実行するために使用され、検出手段が、所定の条件が満たされるまで、上記の検出を複数回反復して繰り返す、検出手段と、最後の反復における第Ｄの最尤検出器の出力に基づいて、スパース信号ベクトル内の原シンボルを推定するための推定手段とをさらに備える。
【０１５９】
具体的には、第ｄの次元について、検出手段内の第ｄの最尤検出器が、スパース信号ベクトル内の原シンボルの事後情報を生成するために、第ｄの次元の測定シンボルと第ｄの次元における先行情報とに基づいて、最尤検出を実行するために使用され、第ｄの次元において生成される事後情報が、第（ｍｏｄ（ｄ，Ｄ）＋１）の次元における先行情報を更新するために使用される。
【０１６０】
好ましくは、第ｄの次元における事後情報ｐ（ｄ）（ｘｉ＝Ｘｑ）が、第（ｍｏｄ（ｄ，Ｄ）＋１）の次元における先行情報
【０１６１】
【数８４】
0005693750.tif 000086
を、以下の式
【０１６２】
【数８５】
0005693750.tif 000087
によって更新するために使用され、ここで、ｅ（ｍｏｄ（ｄ，Ｄ）＋１）（ｘｉ＝Ｘｑ）は、先行する反復の第（ｍｏｄ（ｄ，Ｄ）＋１）の次元において生成され、これは、ｑ＝０〜Ｑ−１の場合、第（ｍｏｄ（ｄ，Ｄ）＋１）の次元におけるｘｉがＸｑである外部確率を表し、ｅ（ｍｏｄ（ｄ，Ｄ）＋１）（ｘｉ＝Ｘｑ）は、第１の反復において１に初期化され、
【０１６３】
【数８６】
0005693750.tif 000088
である。
【０１６４】
所定の条件は、例えば、以下のいずれかを含むことができる。
−一定の反復回数に達した。
−２つの連続する反復において第Ｄの最尤検出器において生成された事後確率の間の差が事前定義された閾値を下回った。
【０１６５】
有利には、スパース信号がアナログ・スパース信号である場合、回復手段は、
ｄ＝１〜Ｄ、ｊ＝１〜Ｊの場合、
【０１６６】
【数８７】
0005693750.tif 000089
内の各要素
【０１６７】
【数８８】
0005693750.tif 000090
について、
【０１６８】
【数８９】
0005693750.tif 000091
が０に等しいかどうかを判断するための判断手段であって、
【０１６９】
【数９０】
0005693750.tif 000092
が、
【０１７０】
【数９１】
0005693750.tif 000093
と初期化され、
【０１７１】
【数９２】
0005693750.tif 000094
が０に等しい場合、ｌ＝１〜Ｌとして、
【０１７２】
【数９３】
0005693750.tif 000095
と設定し、
ここで、Πｄ（ｉ）は、第ｄの置換結果におけるｘｉのインデックスであり、
【０１７３】
【数９４】
0005693750.tif 000096
は、Πｄ（ｉ）の逆操作であり、
ｉ＝１〜Ｎである、スパース信号ベクトルｘ内の各原シンボルｘｉに対して、
以下の式
【０１７４】
【数９５】
0005693750.tif 000097
が満たされるかどうかを判断し、
（ｄｍ，ｄｎ）のペアについて満たされる場合、
【０１７５】
【数９６】
0005693750.tif 000098
と設定し、
ここで、
【０１７６】
【数９７】
0005693750.tif 000099
および
【０１７７】
【数９８】
0005693750.tif 000100
である、判断手段と、
回復されたスパース信号を、以下の式
【０１７８】
【数９９】
0005693750.tif 000101
によって、測定ベクトルｙから減算することによって、
【０１７９】
【数１００】
0005693750.tif 000102
を更新するための更新手段であって、
ここで、
【０１８０】
【数１０１】
0005693750.tif 000103
は、未回復のシンボルが０に設定された、回復されたスパース信号ベクトルを表し、
判断手段が、所定の条件が満たされるまで、上述の判断を複数回反復して繰り返す、更新手段と
をさらに備えてもよい。
【０１８１】
所定の条件は、例えば、以下のいずれかを含むことができる。
−一定の反復回数に達した。
−スパース信号ベクトル内のすべての原シンボルの回復に成功した。
−
【０１８２】
【数１０２】
0005693750.tif 000104
、ここで、
【０１８３】
【数１０３】
0005693750.tif 000105
および
【０１８４】
【数１０４】
0005693750.tif 000106
は、１つの反復の前後の
【０１８５】
【数１０５】
0005693750.tif 000107
を表す。
【０１８６】
上で説明した実施形態は、本発明を限定するためではなく、説明するために与えられたことに留意されたく、また当業者が容易に理解するように、本発明の主旨および範囲から逸脱することなく、変更および変形を施すことができることを理解されたい。そのような変更および変形は、本発明および添付の特許請求の範囲内にあると見なされる。本発明の保護範囲は、添付の特許請求の範囲によって確定される。加えて、特許請求の範囲内の参照番号はいずれも、特許請求の範囲に対する限定と解釈すべきではない。動詞「ｃｏｍｐｒｉｓｅ（含む、備える）」およびその活用形の使用は、請求項内で述べられた要素またはステップ以外の要素またはステップの存在を排除するものではない。要素またはステップの前に置かれる不定冠詞「ａ」または「ａｎ」は、複数のそのような要素またはステップの存在を排除するものではない。
【図１】
0005693750.tif 000160
【図２】
0005693750.tif 000161
【図３ａ】
0005693750.tif 000162
【図３ｂ】
0005693750.tif 000163
【図４】
0005693750.tif 000164
【図５】
0005693750.tif 000165
【図６ａ】
0005693750.tif 000166
【図６ｂ】
0005693750.tif 000167