(57)【要約】【課題】符号測定値ｙから信号ｘを再構築するための方法を得る。【解決手段】信号ｘがスパース符号測定値ｙから再構築される。推定測定値    【数１】2011097570.tif 000041は、    【数２】2011097570.tif 000042にしたがって、前記前回の推定値    【数３】2011097570.tif 000043および測定行列Φから得られる。一貫性のある測定値に訂正信号が適用され、それによって一貫性のある再構築を実行することができる。【選択図】図２
2011097570.tif 000002
【特許請求の範囲】
【請求項１】
符号測定値ｙから信号ｘを再構築するための方法であって、
【数１】
2011097570.tif 000030
は再構築信号ｘの現在の推定値であり、該方法は、反復ｌごとに、前記現在の推定値が前回の推定値
【数２】
2011097570.tif 000031
に収束するまで、
【数３】
2011097570.tif 000032
にしたがって、前記前回の推定値
【数４】
2011097570.tif 000033
および測定行列Φを使用して測定値
【数５】
2011097570.tif 000034
を推定するステップと、
ベクトルｒにおいて、前記推定測定値
【数６】
2011097570.tif 000035
と一貫しない符合を有する符号測定値ｙを識別するステップと、
ｓ＝ΦＴｒｌにしたがって訂正信号を確定するステップと、
【数７】
2011097570.tif 000036
にしたがって前記訂正信号ｓのためのサポート集合Ｔｌを識別するステップであって、ここで、ｓｕｐｐ（・）はサポート集合Ｔｌを確定し、（・）｜２Ｋは、前記信号ｘの、最大の大きさを有する２Ｋ個の成分を選択し、信号ｘのすべての他の成分を０にセットする、識別するステップと、
‖ｘ‖２＝１、およびｘ｜Ｔｃ＝０となるような
【数８】
2011097570.tif 000037
にしたがって一貫性がある再構築を実行するステップであって、ここで、｜Ｔは前記サポート集合内の要素を表し、｜Ｔｃは該サポート集合内にない要素を表す、実行ステップと、
前記現在の推定値
【数９】
2011097570.tif 000038
を更新するステップと、
を含み、前記推定するステップ、前記識別するステップ、前記確定するステップ、前記識別するステップ、前記実行ステップ、および前記更新するステップはコンピュータシステム内で実行される、方法。
【請求項２】
前記信号ｘは任意の基底においてＫ−スパースである、請求項１に記載の方法。
【請求項３】
前記信号ｘは圧縮可能である、請求項１に記載の方法。
【請求項４】
前記再構築はｌ２ノルムを強制する、請求項１に記載の方法。
【請求項５】
前記推定するステップは
【数１０】
2011097570.tif 000039
を使用し、ここで、関数ｄｉａｇは前記符号測定値ｙの対角行列を構築し、前記確定するステップはｓ＝ΦＴｄｉａｇ（ｙ）ｒを使用する、請求項１に記載の方法。
【請求項６】
前記識別するステップは、負の要素
【数１１】
2011097570.tif 000040
のみを保持し、
すべての正の要素をゼロにセットすることをさらに含む、請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、包括的にはスパース信号を再構築することに関し、特に、信号測定値の符号からスパース信号を再構築することに関する。
【背景技術】
【０００２】
任意の信号を誤りなく表現するために、信号が最高周波数の少なくとも２倍（ナイキストレート）で測定されなくてはならないことが知られている。しかしながら、測定後、或る特定の信号が圧縮され得ることが知られている。そのような信号を測定し、その後該信号を圧縮することは、資源を無駄にすることがわかっている。その代わりに、圧縮検知を使用して、スパースであるかまたは圧縮可能である信号を効率的に取得および再構築することができる。圧縮検知は、信号の構造を利用して、ナイキストレートよりも大幅に低いレートでの測定を可能にする。圧縮検知は、ランダム測定、線形測定、非適応型測定を使用することができ、その後に、凸最適化、特にｌ１ノルム最小化を使用するか、または欲張り探索を使用する非線形再構築が続く。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
信号のデジタル測定値は、有限数のビット、たとえば最上位（符号）ビットのみに量子化される。しかしながら、１ビット測定値から信号を再構築することは困難である。１つの方法は、一貫性のある再構築の原理を、単位球面上のｌ１ノルム最小化と組み合わせて信号を再構築する。
【０００４】
この発明の実施の形態１は、欲張り探索を一貫性のある再構築と組み合わせることによって、量子化された信号を再構築するための方法を提供する。各反復において、欲張り探索は局所最適値を選択し、最終的に大域最適を求める。
【課題を解決するための手段】
【０００５】
この発明は、測定行列Φの行との内積を使用して、信号ベクトルｘの線形測定値を処理する。各測定値は、ｙにおいて１符号ビットに量子化される。
【０００６】
ｙ＝ｓｉｇｎ（Φｘ）                    （１）
【０００７】
ここで、関数ｓｉｇｎ（ｙｌ）＝ｙｌ／｜ｙｌ｜は、要素単位で（ｅｌｅｍｅｎｔ−ｗｉｓｅ）測定値Φｘに適用され、信号ベクトルｘはＫ−スパースであるか、または標準基において圧縮可能である。この発明全体を通じて、ｘ＝Ｂａを使用する別の基底においてスパースである信号に関してこの発明を具現化することが可能である。ここで、Ｂは基底行列であり、ａは基底行列Ｂを使用して信号を構成するスパース係数の再構築されたベクトルである。
【０００８】
この発明は、従来技術におけるように、ｌ１ノルム最小化を使用する代わりに、反復的な欲張り探索および一貫性のある再構築を使用する。一貫性のある再構築をスパース性推定と組み合わせることによって、スパース信号の再構築の性能を大幅に向上させることができる。一貫性は、符号に対して強制（ｅｎｆｏｒｃｅ）される。
【発明の効果】
【０００９】
この発明は、信号の測定値の符号から、符号の一貫性制約およびノルム制約を強制しながら、スパースであり且つ圧縮可能な信号を再構築するための方法を提供する。本方法は、各反復において局所最適を選択することによる欲張り法である。再構築方法は、従来技術を上回る幾つかの利点を有し、ｌ１ノルム最小化に基づく一貫性のある再構築を使用する。
【００１０】
反復の間、信号推定値
【００１１】
【数１】
2011097570.tif 000003
【００１２】
が、測定される信号ｘと等しくなる場合、本方法は、正しい解を伴って終了することが保証される。これはそのような保証を提供しない従来技術と対照的である。
【００１３】
第２に、従来技術と対照的に、再構築は常にスパースな解を返す。
【００１４】
第３に、従来技術と対照的に、本方法は、ｌ１ノルムに依存せずに再構築信号のスパース性を測定する。したがって、本方法は、ｌ２ノルムの代わりにｌ１ノルムを正規化制約として使用することができる。本方法を、解が
【００１５】
【数２】
2011097570.tif 000004
【００１６】
を満たすように変更することが可能である。
【００１７】
第４に、本方法は、従来のｌ１ノルムに基づく方法よりも、より一貫性があり、より良好な性能を有する。
【００１８】
本方法は、スパース性およびノルム制約を強制しない従来技術の方法よりも大幅に性能が優れている。従来技術の再構築と比較すると、高ビットレートにおいて利得が１２ｄＢ〜２０ｄＢとなり得る。
【図面の簡単な説明】
【００１９】
【図１】この発明の実施の形態１による、符号測定値からスパース信号を再構築するための方法の擬似コードのブロック図である。
【図２】図１の方法のブロック図である。
【図３】図１の方法が使用することができるベクトルおよび行列演算の概略図である。
【図４】図１の方法が使用することができるベクトルおよび行列演算の概略図である。
【発明を実施するための形態】
【００２０】
図１〜図４に示すように、この発明の実施の形態１は、信号ベクトルｘを再構築するための反復的な方法を提供する。ベクトルｘは標準基に置いてＫ−スパースである。慣習により、Ｋは非ゼロ要素の最大の数を示す。再構築はｌ２（ユークリッド）ノルムを強制する。
【００２１】
本方法は、各反復ｌの後、再構築信号
【００２２】
【数３】
2011097570.tif 000005
【００２３】
の現在の推定値
【００２４】
【数４】
2011097570.tif 000006
【００２５】
および該推定値のスパースサポートを作成する。特に、測定行列
【００２６】
【数５】
2011097570.tif 000007
【００２７】
の行との内積を使用する信号
【００２８】
【数６】
2011097570.tif 000008
【００２９】
の線形測定値を検討する。各測定値は、測定値ベクトルにおける符号ビットのみを保持することによって１ビットに量子化される。本方法のステップは、当該技術分野において既知のメモリおよびＩ／Ｏインタフェースを備えるプロセッサ２００において実行することができる。
【００３０】
入力−２０１：測定行列Φ３０２内の信号測定値Φｘの符号の測定値ベクトルｙ｛±１｝３００、およびスパース性Ｋ。
【００３１】
初期化２０２：反復カウントｌ＝０、および再構築信号
【００３２】
【数７】
2011097570.tif 000009
【００３３】
の現在の推定値
【００３４】
【数８】
2011097570.tif 000010
【００３５】
３０３。
【００３６】
ステップ１−２１０：収束していない間（Ｗｈｉｌｅ）以下を行う（ｄｏ）
【００３７】
ステップ２−２２０：反復カウントを増加させる  ｌ←ｌ＋１
【００３８】
ステップ３−２３０：前回の反復における再構築信号の推定値
【００３９】
【数９】
2011097570.tif 000011
【００４０】
を使用して、測定値
【００４１】
【数１０】
2011097570.tif 000012
【００４２】
を推定する。
【００４３】
図３を参照すると、第１の実施の形態１では、これは
【００４４】
【数１１】
2011097570.tif 000013
【００４５】
にしたがって行われる。ここで、関数ｄｉａｇは、ベクトルｙの対角行列３０１を構築する。推定測定値は、測定値
【００４６】
【数１２】
2011097570.tif 000014
【００４７】
のすべての要素が正である場合に一貫性がある。
【００４８】
図４を参照すると、第２の実施の形態１では、これは
【００４９】
【数１３】
2011097570.tif 000015
【００５０】
にしたがって行われる。推定測定値は、
【００５１】
【数１４】
2011097570.tif 000016
【００５２】
のすべての要素が、ベクトルｙの対応する要素と同じ符号を有する場合に一貫性がある。
【００５３】
図３は、対角上に測定値ベクトルｙにおける符号を含む対角行列ｄｉａｇ（ｙ）３０１、および測定行列Φ３０２を示している。第１の実施の形態１では、推定値は
【００５４】
【数１５】
2011097570.tif 000017
【００５５】
である。図４は第２の実施の形態１を示している。ここで、対角行列３０１が省かれている。
【００５６】
ステップ４−２４０：
【００５７】
【数１６】
2011097570.tif 000018
【００５８】
にしたがって、推定測定値
【００５９】
【数１７】
2011097570.tif 000019
【００６０】
３００と一貫しない符合を有するベクトルｙ内の測定値に関して、ベクトルｒにおける符号非一貫性を識別する。
【００６１】
図３に示す実施の形態１において、ベクトルｒはステップ３の出力の負の要素
【００６２】
【数１８】
2011097570.tif 000020
【００６３】
のみを格納する。ここで、（・）−は、
【００６４】
【数１９】
2011097570.tif 000021
【００６５】
の負の要素を示し、すべての正の要素はゼロにセットされる。
【００６６】
図４に示す第２の実施の形態１では、ベクトルｒは、ベクトルｙ内の対応する要素と逆の符号を有するベクトル
【００６７】
【数２０】
2011097570.tif 000022
【００６８】
の要素を格納し、同じ符号を有するすべての要素をゼロにセットする。
【００６９】
ステップ５−２５０：ステップ３において対角行列が使用されている場合にはｓ＝ΦＴ  ｄｉａｇ（ｙ）ｒにしたがい、対角行列が使用されていない場合にはｓ＝Φ＝ΦＴｒにしたがって、訂正信号ｓを確定する。訂正信号を使用して、推定測定値
【００７０】
【数２１】
2011097570.tif 000023
【００７１】
における符号を一貫性のあるものにする。
【００７２】
ステップ６−２６０：
【００７３】
【数２２】
2011097570.tif 000024
【００７４】
にしたがって訂正信号ｓのためのサポート集合を識別する。ここで、ｓｕｐｐ（・）はサポート集合を確定し、（・）｜Ｌは、訂正信号ｓの、最大の大きさを有するＬ個の成分を選択し、すべての他の成分を０にセットする。サイズＬは、測定行列Φの特性に依拠する方法のパラメータである。この発明では、Ｋ＜Ｌ≦２Ｋが好ましい。Ｌがそれより小さいと、再構築がはるかに低速になり得る。Ｌがそれより大きいと、再構築の精度が下がるかまたは方法が正しく収束する確率が低減し得る。
【００７５】
ステップ７−２７０：以下の最適化
【００７６】
【数２３】
2011097570.tif 000025
【００７７】
を使用して、サポートＴに対する一貫性のある再構築を実行する。ここで、ｂｌは最適化の結果であり、ｂｌ｜Ｔはサポート集合Ｔ内のｂｌの要素を表し、ｂｌ｜Ｔｃはサポート集合内にない要素を表す。表記‖・‖２はｌ２ノルム、すなわち総信号エネルギーを表し、
【００７８】
【数２４】
2011097570.tif 000026
【００７９】
はｌ２ノルムの二乗を表す。
【００８０】
すなわち、正規化制約を受ける、ベクトルの一貫性のない部分内の二乗ノルムが最小化される。最小化は、図４の実施の形態１と同様に、非対角形式Φｘの一貫性のない部分に対しても実行することができる。
【００８１】
ステップ８−２８０：
【００８２】
【数２５】
2011097570.tif 000027
【００８３】
にしたがって、訂正を切り捨て、正規化し、更新する。
【００８４】
出力−２０９：再構築信号
【００８５】
【数２６】
2011097570.tif 000028
【００８６】
。
【００８７】
測定プロセス
測定プロセスは、測定値の符号のみを記録し、すべてのα＞０について、ｓｉｇｎ（Φｘ）＝ｓｉｇｎ（Φαｘ）とし、大きさを破棄する。したがって、再構築の間、振幅制約
【００８８】
【数２７】
2011097570.tif 000029
【００８９】
が課され、そうでない場合はｘ＝０が一貫性があるものとなるが望ましくない解である。このため、各反復の後に信号を正規化することによってｌ２ノルム制約が強制される。
【００９０】
しかしながら、信号を正規化する他の方法および制約を使用することができる。例は、信号を予め特定されるｌ１ノルムを有するように正規化すること、信号を予め特定されるｌ∞ノルムを有するように正規化すること、信号を特定の係数または係数の線形結合が予め特定される値を有するようにスケーリングすること、または信号を予め特定される平面に投影することを含むがこれらに限定されない。
【００９１】
この発明を好ましい実施の形態１の例として説明してきたが、この発明の精神および範囲内で様々な他の適応および変更を行うことができることは理解されたい。したがって、添付の特許請求の範囲の目的は、この発明の真の精神および範囲内に入るすべての変形および変更を包含することである。
【図１】
2011097570.tif 000044
【図２】
2011097570.tif 000045
【図３】
2011097570.tif 000046
【図４】
2011097570.tif 000047
【外国語明細書】
2011097570.tif 000048
2011097570.tif 000049
2011097570.tif 000050
2011097570.tif 000051
2011097570.tif 000052
2011097570.tif 000053
2011097570.tif 000054
2011097570.tif 000055
2011097570.tif 000056
2011097570.tif 000057
2011097570.tif 000058
2011097570.tif 000059
2011097570.tif 000060
2011097570.tif 000061
2011097570.tif 000062