(57)【要約】      （修正有）【課題】単調性のある非線形歪みを受けた測定値から、正確な信号を再構築する。【解決手段】信号ｘが、当該信号ｘを測定値ｙｉのベクトルｙとして測定することにより再構築される。測定値ｙｉは歪みを受け、各測定値ｙｉは関連した値を有する。ベクトルｙにおける測定値ｙｉは、関連した値に従って順序付けられ、各ソートされた測定値は、順序付けられたインデックスシーケンスを形成する順序付けに対応するインデックスを有する。次に、ＭＭＳＥ推定またはＭＳＰ符号追跡手順に基づく再構築方法が、順序付けられたインデックスシーケンスに適用され、信号ｘの推定値(ハット)Ｘが生成される。【選択図】図１
2011096240.tif 000002
【特許請求の範囲】
【請求項１】
信号ｘを再構築するための方法であって、
測定値ｙｉのベクトルｙとして信号ｘを測定するステップであって、該測定値ｙｉは歪みを受け、各測定値ｙｉは、関連した値を有するものと、
前記関連した値に従って前記ベクトルｙにおける前記測定値ｙｉを順序付けるステップであって、各ソートされた測定値は、順序付けられたインデックスシーケンスを形成する前記順序付けに対応するインデックスを有するものと、
前記順序付けられたインデックスシーケンスに再構築方法を適用するステップであって、前記信号ｘの推定値
【数１】
2011096240.tif 000036
を生成し、前記信号ｘはスパースであるものと、
を含む方法。
【請求項２】
前記歪みは非線形且つ未知である、請求項１に記載の方法。
【請求項３】
前記非線形性は単調である、請求項２に記載の方法。
【請求項４】
前記ベクトルｙにおける前記測定値ｙｉは正規分布ｆ(ｙ)に従い、該正規分布ｆ(ｙ)は、累積分布関数(ＣＤＦ)Φ(ｙ)である、請求項１に記載の方法。
【請求項５】
前記順序付けは増加順である、請求項１に記載の方法。
【請求項６】
前記順序付けは減少順である、請求項１に記載の方法。
【請求項７】
前記測定することは、
ｙ＝ｇ(Ａｘ)
に従い、ここでＡは測定行列であり、前記関数ｇは非線形増加又は非線形減少するものであり、前記信号ｘに要素単位に適用される、請求項１に記載の方法。
【請求項８】
前記測定値の個数はＭであり、前記適用することは、
測定値
【数２】
2011096240.tif 000037
を
【数３】
2011096240.tif 000038
に従って推定することをさらに含み、ここでｐｉ＝ｉ／(Ｍ＋１)であり、圧縮再構築は
【数４】
2011096240.tif 000039
であり、ここでΔＡは再構築手順である、請求項４に記載の方法。
【請求項９】
前記適用することは、
前記測定値ｙｉの前記順序付けに対する一貫性のある制約
【数５】
2011096240.tif 000040
を充足すること、をさらに含み、ここで、
【数６】
2011096240.tif 000041
は測定行列であり、ｓｉｇｎ(・)＝±１であり、ｉ及びｊは前記行列
【数７】
2011096240.tif 000042
を形成するのに使用される前記測定行列Ａのそれぞれ第１の行のインデックス及び第２の行のインデックスであり、圧縮再構築は、
【数８】
2011096240.tif 000043
であり、ここで、ＭＳＰは、マッチング符号追跡手順である、
請求項７に記載の方法。
【請求項１０】
前記値は前記信号ｘの振幅である、請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、包括的には、スパース信号を再構築することに関し、より詳細には、歪みを受けた測定値からスパース信号を再構築することに関する。
【背景技術】
【０００２】
誤差なしに信号を表すには、信号を、その最も高い周波数の少なくとも２倍のレート(ナイキストレート)で測定しなければならない。しかしながら、ある一定の信号は、測定後に圧縮される可能性があり、このことは、信号がナイキストレートで測定され、その後に圧縮される場合に資源を浪費することになる。
【０００３】
代わりに、圧縮センシング(ＣＳ)を使用して、スパース信号又は圧縮可能信号を効率的に取得して再構築することができる。ＣＳは、ナイキストレートよりもかなり低いレートでの信号測定の構造を使用して、再構築を行う。ＣＳは、ランダム測定、線形測定又は非適応測定を使用することができ、その後に凸最適化又は欲張り探索を使用した非線形再構築が続く。
【０００４】
ＣＳを有しない従来の解決法は、ｌ２ノルム、すなわちシステムにおけるエネルギー量を最小にするものである。しかしながら、これは、測定された信号におけるスパース性を考慮しないので、ほとんどの実用的な用途に質の悪い結果をもたらす。所望のＣＳ解決法は、ｌ０ノルムを最小にすべきであり、これによって、このスパース性が測定される。しかしながら、これは、ＮＰ困難な問題である。したがって、通例、ｌ１ノルムが最小にされ、これによっては、スパース性も促進され、一定の条件下では、ｌ０ノルムと等価であることを証明することができる。最小のｌ１ノルムを有する候補を見つけることは、線形問題として表すことができ、この線形問題には、効率的な解決法が存在する。
【０００５】
ＣＳを使用すると、Ｋ個の非ゼロの係数を有する信号ｘは、
ｙ＝Ａｘ          (１)
を使用して得られる線形非適応測定値から再構築することができる。ここで、Ａは、測定行列である。正確な信号再構築は、測定行列Ａが制限付き等長性(ＲＩＰ)を有するときに保証される。ＲＩＰは、少なくともスパース信号に作用するときに正規直交行列と同様に振舞う行列を特徴付けるものである。行列Ａは、２Ｋ個のすべてのスパース信号ｚについて、
【０００６】
【数１】
2011096240.tif 000003
【０００７】
となるような定数Δ２Ｋが存在する場合に、次数２ＫのＲＩＰを有する。
【０００８】
Δ２Ｋが小さい場合、行列Ａは、Ｋ個のスパース信号間にｌ２ノルム距離をほぼ保持する。この場合、凸最適化は、
【０００９】
【数２】
2011096240.tif 000004
【００１０】
を条件として信号を再構築する。
【００１１】
一代替的な方法は、欲張りスパース再構築手順を使用する。最適化方法と同様に、その保証となるものは、行列ＡのＲＩＰに基づいている。驚くべきことに、十分な行数を有するランダム行列は、圧倒的な確率で小さなＲＩＰ定数を達成することができる。したがって、ランダム行列は、ＣＳ信号の取得及び再構築に一般に使用される。
【００１２】
取得行列のランダム性によっても、測定値の整形式の統計分布が保証される。具体的には、行列が独立同一分布(ｉ．ｉ．ｄ．)ランダムエントリーを有する場合、ベクトルｙにおける測定値も漸近正規分布(asymptotic, normal distribution)に従う。
【００１３】
信号の測定値は、有限個のビットに量子化することができ、例えば、最上位(符号)ビットのみに量子化することができる。しかしながら、量子化された測定値からの信号の再構築は困難である。当該技術における１つの方法は、一貫性のある再構築(consistent reconstruction)の原理を、単位エネルギーの球面上のｌ１ノルム最小化と組み合わせて、信号を再構築するものである。具体的には、信号は、
ｙ＝ｓｉｇｎ(Ａｘ)          (４)
を使用して測定される。ここで、ｓｉｇｎ(・)＝±１である。再構築された信号は、測定値の符号と一貫性がある。
【００１４】
測定値の符号は、信号の大きさについてあらゆる情報を取り除くので、単位エネルギー||ｘ||２＝１の制約が、再構築中に課せられる。すなわち、再構築は、単位球面上で実行される。スパース性は、単位エネルギーの球面上でｌ１ノルムを最小にすることによって強制される。
【００１５】
測定値との一貫性は、厳格な制約を緩和し、制約が破られたときに一方的な二次ペナルティを導入することによって課される。これは、制約を違反する測定値の二乗ノルムとして表すことができる。具体的には、スカラーの負部が(・)によって示される。すなわち、
【００１６】
【数３】
2011096240.tif 000005
【００１７】
次に、ペナルティは、
【００１８】
【数４】
2011096240.tif 000006
【００１９】
である。ここで、ｄｉａｇ(ｙ)は、対角線上に測定値の符号を有する行列である。負演算子(・)−は、要素単位に適用されて、制約違反及び違反の振幅を識別する。
【００２０】
測定値と一貫性がある信号の推定値は、制約違反を生成せず、ペナルティ
【００２１】
【数５】
2011096240.tif 000007
【００２２】
は０である。式(６)を使用すると、再構築問題は、
【００２３】
【数６】
2011096240.tif 000008
【００２４】
となる。
【００２５】
式(７)は、非凸であり、大域的最適解への収束を保証することはできない。
【００２６】
欲張り探索手順は、ペナルティ関数に関するスパース最小値を欲張って求めようと試みる。マッチング符号追跡(ＭＳＰ(Matching Sign Pursuit))手順は、圧縮サンプリングマッチング追跡(ＣｏＳａＭＰ(Compressive Sampling Matching Pursuit))、及び部分空間追跡と同様の反復的な欲張り探索を実行する。具体的には、ＭＳＰ手順は、反復によって信号ｘのスパース推定値を更新する。これについては、関連出願を参照されたい。ＭＳＰは、ＣｏＳａＭＰをかなり修正して、一貫性制約(consistency constraint)及びｌ２単位エネルギー制約を強制することにより測定値の符号のみを使用して再構築を可能にする。
【発明の概要】
【発明が解決しようとする課題】
【００２７】
この発明の実施の形態は、非線形性がたとえ未知であっても単調である場合には、非線形歪みを受けた測定値からスパース信号を再構築するための方法を提供する。非線形性は単調であるので、この方法は、歪みを受けた測定値において信頼できる情報を使用する。この情報は、測定値の振幅に基づいた順序付けである。順序付けられた振幅は、高精度でスパース信号を再構築するのに十分である。
【課題を解決するための手段】
【００２８】
一実施の形態は、順序付けられた振幅の順序統計量を使用して、歪みを受けていない測定値の最小平均二乗(ＭＭＳＥ)推定値を求め、任意の従来の圧縮センシング(ＣＳ)再構築手順と共にＭＭＳＥを使用する。
【００２９】
別の実施の形態は、再構築された信号の測定値の振幅が、歪みを受けた測定値の振幅の順序付けと一貫性がある順序付けを有することを保証する決定性非線形再構築手順における一貫性のある再構築の原理を使用する。
【発明の効果】
【００３０】
この発明の実施の形態は、測定値の未知の単調非線形歪みを受けるスパース信号を再構築する。驚くべきことに、この歪みは、信号を再構築するのに十分な情報を保持する。キーとなるアイデアは、歪みが単調であるので、信号値の相対的な順序付けが保存されるということである。順序付けは、信号再構築のための十分な情報を保存する。
【００３１】
一実施の形態は、歪みを受けた測定値の順序統計量を使用して歪みを受けていない測定値を推定する統計的枠組みを使用する。測定値は、信号を再構築する任意の再構築手順に入力することができる。
【００３２】
別の実施の形態は、再構築手順に順序付け情報を直接組み込む決定性枠組みを使用する。この枠組みでは、欲張り再構築手順が、測定値順序付けの情報と一貫性のある信号推定値を生成する。
【００３３】
双方の実施の形態は、歪みを受けた測定値の従来のＣＳ再構築よりも良好な性能を有する。
【００３４】
１つのアイデアは、ランダム化された測定プロセスを利用することである。ランダム化によって、個々の測定値は、正規分布の確率変数となる。標準的な推定理論が、順序統計量と組み合わせられて、歪みを受けていない測定値の最小平均二乗誤差(ＭＭＳＥ)推定値を求める。この推定値は、歪みを受けた測定値の順序付けにのみ基づく。信号の構造に関する仮定も、再構築手順に関する仮定も行われない。この発明は、ＣＳのコンテキストで説明されるが、この発明は、適切な再構築手順を使用して、信号のランダム化され歪みを受けた測定値からさまざまな信号を再構築するのに使用することもできる。
【００３５】
別のアイデアは、非線形再構築を使用することである。この非線形再構築は、制約として測定値の順序付けを再構築プロセスに組み込む。したがって、この発明は、信号構造の従来の知識に加えて、測定システムの知識も利用する。
【００３６】
この発明の用途は数多くある。測定デバイスの非線形特性のドリフト及び変動は、ほとんどの取得システムにおいて一般的であり、製造条件及びランタイム条件に起因して変動する。例えば、光学系では、動作温度及び周囲光が、デバイスを、取得の非線形領域にドリフトさせる可能性がある。
【図面の簡単な説明】
【００３７】
【図１】この発明の実施の形態による信号の振幅の順序付けに基づいてスパース信号を再構築するための方法のフロー図である。
【図２】この発明の実施の形態による信号の振幅の順序付けに基づいてスパース信号を再構築するための方法のフロー図である。
【図３】図２を参照して説明した方法によって使用されるマッチング符号追跡手順のための従来技術の疑似コードである。
【発明を実施するための形態】
【００３８】
この説明において、次の従来のシンボルが変数の上部に使用される。この説明及び特許請求の範囲におけるこれらのシンボルは、明瞭にするために省略される場合がある。
【００３９】
【数７】
2011096240.tif 000009
【００４０】
は推定値であり、
【００４１】
【数８】
2011096240.tif 000010
【００４２】
は平均であり、
【００４３】
【数９】
2011096240.tif 000011
【００４４】
は作業用の推定値(working estimate)である。
【００４５】
図１に示すように、この発明の一実施の形態は、非線形歪みを受けたスパース信号ｘの測定ベクトルｙ  １０１及び測定行列Ａ  １０２からスパース信号の推定値
【００４６】
【数１０】
2011096240.tif 000012
【００４７】
１０９を再構築するための方法を提供する。この方法のステップは、当該技術で知られているようにメモリ及び入出力インターフェースを含むプロセッサにおいて実行することができる。
【００４８】
順序統計量
ベクトルｙにおける測定値ｙｉは、ｆ(ｙ)で示される正規分布に従う。この正規分布は、Φ(ｙ)で示される累積分布関数(ＣＤＦ)である。ＣＤＦは、変数が所与の値以下である確率を示す。
【００４９】
Ｍ個の測定値ｙｉ  １０１は、その振幅、すなわち、
【００５０】
【数１１】
2011096240.tif 000013
【００５１】
の順序に順序付けられる(１１０)。振幅の順序は、増加順又は減少順とすることができ、例えばｙ(１)≦ｙ(２)≦…≦ｙ(Ｍ)とすることができる。この順序付けにおいて、下付き文字(ｉ)は、順序付けのインデックスであり、ｋｉは、順序付けされていない対応する測定値のインデックスである。
【００５２】
ソートされた振幅は、測定値の順序統計量を形成する。変数ｐｉ＝１／(Ｍ＋１)及びｑｉ＝１−ｐｉは、測定値ｙ(ｉ)の振幅よりもそれぞれ小さい振幅及び大きい振幅を有する測定値の確率を漸近的に占める。
【００５３】
一般に、順序統計量のモーメントは、閉形式を有しない。漸近的に正確な非バイアス近似値は、
【００５４】
【数１２】
2011096240.tif 000014
【００５５】
である。ここで、Ｑ(ｘ)＝Φ−１(ｘ)は、ＣＤＦの逆関数であり、分位関数と呼ばれることが多く、Ｑ’(ｘ)は、ｘにおいて求められた導関数である。確率分布の分位関数は、その値よりも下にランダム選択値がその時間のｐ×１００％含まれる値を返す。
【００５６】
測定モデル
この発明の実施の形態は、測定行列Ａの行ａｉとの内積を使用したスパース信号ｘの線形測定値を考える。この測定値は、
ｙ＝ｇ(Ａｘ)          (１１)
である。ここで、関数ｇは、非線形に増加又は減少し、要素単位に、信号ベクトルｘの要素の係数に適用される。
【００５７】
非線形歪みは未知であるので、限られた情報しかｇ(・)によって提供されない。例えば、未知の歪みｇ(ｘ)は、信号ｘのあらゆる振幅情報を取り除く。したがって、信号ｘは、正のスカラーファクタ内でのみ再構築することができる。さらに、２つの単調関数を合成したものも単調であるので、測定値の他のどの単調歪みも、同じ信号が起源である可能性がある。非線形性は、測定値の振幅の順序付けを維持する。
【００５８】
順序付け特性がこの発明によって利用される。式(８)及び順序付け特性から、
ｓｉｇｎ(ｙ(ｉ)−ｙ(ｊ))＝ｓｉｇｎ(ｉ，ｊ)          (１２)
ということになる。
【００５９】
インデックスシーケンス｛ｋ１，…，ｋＭ｝は、恒等を含めて、すべての単調歪みｇ(ｘ)間で保存される。さらに、シーケンス｛ｋｉ｝が判明した後、ｙ(ｉ)の正確な値は、それ以上の情報を提供せず、再構築中に使用されない。これは、ｙ(ｉ)を、同じ順序付け｛ｋｉ｝を有する他の任意のｙ(ｉ)にマッピングする非線形単調歪みを常に構成できるからである。
【００６０】
測定行列Ａにおける要素はランダムであり、正規分布をしているので、歪みを受けていない測定値もランダムであり、正規分布をしている。漸近的に、これは、中心極限定理によって、たとえ行列のエントリーがランダム独立同一分布であるが正規分布をしていない場合であっても当てはまる。
【００６１】
測定値置換
測定値の順序の統計量は、スパース信号ｘの推定値
【００６２】
【数１３】
2011096240.tif 000015
【００６３】
を再構築するのに使用される。非線形性ｇ(・)は未知であるので、測定値の振幅の順序付けは、測定ベクトルｙから得られた唯一の信頼できる情報である。歪みを受けていない測定値のランダム性及び正規性を使用すると、歪みを受けていない測定値の推定器が提供される。
【００６４】
歪みを受けた測定値を使用する代わりに、歪みを受けた測定値は、測定値の振幅の順序付けのみを条件に、歪みを受けていない値のＭＭＳＥ推定値と取り替えられる。この推定器は、測定値の順序付け
【００６５】
【数１４】
2011096240.tif 000016
【００６６】
の関数である。具体的には、ＭＭＳＥ推定器は、条件付き期待値
【００６７】
【数１５】
2011096240.tif 000017
【００６８】
である。
【００６９】
上記のように、測定プロセスは、信号の順序以外のすべての振幅情報を信号から除去する。したがって、信号は、正のスケーリングファクタ内でのみ識別することができる。再構築された信号は、単位ｌ２ノルムを有するように正規化されるので、測定値は、標準正規分布に従う。
【００７０】
順序付けの後、再構築１２０は次のように進む。式(９)の漸近的近似を式(１３)に使用して、測定値の推定１２１は、逆ＣＤＦ
【００７１】
【数１６】
2011096240.tif 000018
【００７２】
に従う。ここで、Φ(・)は、標準正規分布のＣＤＦ
【００７３】
【数１７】
2011096240.tif 000019
【００７４】
を示す。ここで、ｅｒｆは誤差関数である。
【００７５】
推定された測定値
【００７６】
【数１８】
2011096240.tif 000020
【００７７】
は、信号
【００７８】
【数１９】
2011096240.tif 000021
【００７９】
１０９を
【００８０】
【数２０】
2011096240.tif 000022
【００８１】
として再構築する(１２０)ために任意の再構築手順ΔＡへの入力として使用することができる。
【００８２】
一貫性のある再構築
図２に示すような別の実施の形態では、測定値の順序付けに対する一貫性のある制約２２１が、再構築中に充足される(２２１)。この制約は、再構築された信号の測定値が、入力信号の測定値と同じ順序付けを有することを保証する。したがって、暗黙的な測定行列
【００８３】
【数２１】
2011096240.tif 000023
【００８４】
は、行列Ａ及び
【００８５】
【数２２】
2011096240.tif 000024
【００８６】
となるような測定振幅の順序付けから導出することができる。ここで、ｓｉｇｎ(・)＝±１である。
【００８７】
ａｋが行列Ａの第ｋ行を示す場合、
【００８８】
【数２３】
2011096240.tif 000025
【００８９】
である。ここで、式(１６)は、式(１１)における非線形歪みの単調性から得られ、式(１８)は、式(１２)、すなわち、順序付けられたインデックスシーケンス｛ｋｉ｝の特性から得られる。
【００９０】
換言すれば、行列
【００９１】
【数２４】
2011096240.tif 000026
【００９２】
は、制約
【００９３】
【数２５】
2011096240.tif 000027
【００９４】
が充足される(２２１)ように形態
【００９５】
【数２６】
2011096240.tif 000028
【００９６】
の行列Ａの行を使用して構成することができる。例えば、
【００９７】
【数２７】
2011096240.tif 000029
【００９８】
である。ここで、ｉ及びｊはそれぞれ第１の行のインデックス及び第２の行のインデックスである。
【００９９】
行列
【０１００】
【数２８】
2011096240.tif 000030
【０１０１】
及び対応する符号測定値は、ＭＳＰ手順(上記参照)に入力されて、スパース信号ｘを推定値
【０１０２】
【数２９】
2011096240.tif 000031
【０１０３】
として推定する(２２２)。
【０１０４】
式(１９)は、インデックス対(ｋｉ，ｋｊ)について成立し、したがって、行列
【０１０５】
【数３０】
2011096240.tif 000032
【０１０６】
を構成するように選択されたベクトル対
【０１０７】
【数３１】
2011096240.tif 000033
【０１０８】
について成立する。ｉ＝１，…，Ｍ−１の(Ｍ−１)個の対(ｋｉ＋１，ｋｊ)を使用することによって、再構築があらゆる対(ｋｉ，ｋｊ)と一貫性があることが保証される。これは、推奨される手法である。しかしながら、他の設計選択を使用することが可能である。この設計は、行列
【０１０９】
【数３２】
2011096240.tif 000034
【０１１０】
の行を構成するのに使用される行列Ａの行の対(ｋｉ，ｋｊ)を選択することと等価である。
【０１１１】
再構築の初期シード値は、別の設計選択である。この実施の形態は、非凸問題を解くことを試みるので、正しい初期値によって、大域的最適解への収束が容易になる。たとえＭＳＰ手順が、従来技術で説明した単位球面上でのｌ１最適化よりも良好な収束性能を有する場合であっても、測定値の個数Ｍが少ない場合には、依然として収束問題が存在する可能性がある。したがって、収束を改善するために、測定値置換及び／又は従来のＣＳ復号の少数の反復を使用して、初期値を提供することができる。
【０１１２】
マッチング追跡手順
図３は、図２を参照して説明したＭＳＰ手順のステップを示す。ＭＳＰ手順は、式(６)のペナルティ関数のスパース最小値を見つけることを試みる欲張り探索を使用する。
【０１１３】
具体的には、ＭＳＰ手順は、次の反復を使用して、信号
【０１１４】
【数３３】
2011096240.tif 000035
【０１１５】
のスパース推定値を更新する。
ステップ３及び４は、違反されている符号制約を識別する。
ステップ５及び６は、コスト関数を最小にし、符号違反を低減する際に大部分有効な信号成分を識別する。
ステップ７は、それらの信号成分にわたってコスト関数を最小にする。
ステップ８は、信号を所望のスパース性にトランケートし、推定値を正規化し、更新する。
【０１１６】
この発明を好ましい実施の形態の例として説明してきたが、この発明の趣旨及び範囲内において他のさまざまな適応及び修正を行えることが理解されるべきである。したがって、この発明の真の精神及び範囲内に入るこのようなすべての変更及び修正を包含することが添付の特許請求の範囲の目的である。
【図１】
2011096240.tif 000044
【図２】
2011096240.tif 000045
【図３】
2011096240.tif 000046
【外国語明細書】
2011096240.tif 000047
2011096240.tif 000048
2011096240.tif 000049
2011096240.tif 000050
2011096240.tif 000051
2011096240.tif 000052
2011096240.tif 000053
2011096240.tif 000054
2011096240.tif 000055
2011096240.tif 000056
2011096240.tif 000057
2011096240.tif 000058
2011096240.tif 000059
2011096240.tif 000060
2011096240.tif 000061
2011096240.tif 000062
2011096240.tif 000063
2011096240.tif 000064
2011096240.tif 000065
2011096240.tif 000066