"a.長さMの測定ベクトルyを獲得するために、M×N測定行列Aを用いて、長さNのスパース信号ベクトルx={xi}に対して線形測定を実行するステップであって、前記測定行列Aが、によって表され、ここで、d=1~Dである場合、AdΠdは、前記測定行列Aの部分行列であり、Πdは、N×Nランダム置換行列であり、Adは、によって表されるJ×N行列であり、ここで、M<<N、J×L=Nであり、同じ置換行列から生成された測定シンボルは、1つの次元と呼ばれ、Dは、総次元数である、ステップと、b.前記長さNのスパース信号ベクトルx={xi}を前記長さMの測定ベクトルyから回復するステップとを含む、スパース信号を測定および回復するための方法。前記スパース信号が、デジタルスパース信号であり、前記スパース信号ベクトルx内の各成分xiが、有限集合Q={X0=0,X1,...,XQ-1}から取られ、q=1~Q-1の場合、Xqはゼロ以外の数であり、Qは前記集合のサイズである場合、前記ステップbが、b1.D個の次元に対してそれぞれ最尤検出を実行するために、D個の最尤検出器を使用するステップであって、第dの最尤検出器が、第dの次元に対して最尤検出を実行するために使用される、ステップと、b2.所定の条件が満たされるまで、ステップb1を複数回反復して繰り返すステップと、b3.最後の反復における第Dの最尤検出器の出力に基づいて、前記スパース信号ベクトル内の原シンボルを推定するステップとを含む、請求項1に記載の方法。前記ステップb1が、第dの次元について、前記スパース信号ベクトル内の前記原シンボルについての事後情報を生成するために、第dの次元の測定シンボルと第dの次元における先行情報とに基づいて、最尤検出を実行するステップであって、第dの次元において生成される前記事後情報が、第modd,D1の次元における先行情報を更新するために使用される、ステップを含む、請求項2に記載の方法。第dの次元における事後情報pdxi=Xqが、第modd,D1の次元における先行情報を、以下の式によって更新するために使用され、ここで、emodd,D1xi=Xqは、先行する反復の第modd,D1の次元において生成され、これは、q=0~Q-1の場合、第modd,D1の次元におけるxiがXqである外部確率を表し、emodd,D1xi=Xqは、第1の反復において1に初期化され、後続する反復においてのように更新される、請求項3に記載の方法。前記スパース信号が、アナログスパース信号である場合、前記方法bが、i.d=1~D、j=1~Jの場合、内の各要素について、が0に等しいかどうかを判断するステップであって、が、と初期化され、が、の第dの次元内の第jの要素である、ステップと、ii.が0に等しい場合、l=1~Lとして、と設定するステップであって、ここで、Πdiは、第dの置換結果におけるxiのインデックスであり、は、Πdiの逆操作である、ステップとを含み、前記方法が、u.i=1~Nの場合、前記スパース信号ベクトルx内の各原シンボルxiについて、以下の式が満たされるかどうかを判断するステップと、v.上記の式がdm,dnのペアについて満たされる場合、と設定するステップであって、ここで、およびである、ステップとをさらに含み、上記のステップの後、前記方法が、p.回復されたスパース信号を、以下の式によって、測定ベクトルyから減算することによって、を更新するステップであって、ここで、は、未回復シンボルが0に設定された、回復されたスパース信号ベクトルを表す、ステップと、q.所定の条件が満たされるまで、上記のステップを複数回反復して繰り返すステップとをさらに含む、請求項1に記載の方法。前記所定の条件が、以下のいずれか、すなわち、-一定の反復回数に達した、-2つの連続する反復において第Dの最尤検出器において生成された事後確率の間の差が事前定義された閾値を下回ったを含む、請求項2に記載の方法。前記所定の条件が、以下のいずれか、すなわち、-一定の反復回数に達したこと、-前記スパース信号ベクトル内のすべての原シンボルの回復に成功したこと、-、ここで、およびは、1つの反復の前後のを表すことを含む、請求項5に記載の方法。長さMの測定ベクトルyを獲得するために、M×N測定行列Aを用いて、長さNのスパース信号ベクトルx={xi}に対して線形測定を実行するための測定手段であって、前記測定行列Aが、によって表され、ここで、d=1~Dの場合、AdΠdは、前記測定行列Aの部分行列であり、Πdは、N×Nランダム置換行列であり、Adは、によって表されるJ×N行列であり、ここで、M<<N、J×L=Nであり、同じ置換行列から生成された測定シンボルは、1つの次元と呼ばれ、Dは、総次元数である、測定手段と、前記長さNのスパース信号ベクトルx={xi}を前記長さMの測定ベクトルyから回復するための回復手段とを備える、スパース信号を測定および回復するための装置。前記スパース信号が、デジタルスパース信号であり、前記スパース信号ベクトルx内の各成分xiが、有限集合Q={X0=0,X1,...,XQ-1}から取られ、q=1~Q-1の場合、Xqは、ゼロ以外の数であり、Qは、前記集合のサイズである場合、前記回復手段が、D個の次元に対してそれぞれ最尤検出を実行するためのD個の最尤検出器を含む検出手段であって、第dの最尤検出器が、第dの次元に対して最尤検出を実行するために使用され、前記検出手段が、所定の条件が満たされるまで、上述の検出を複数回反復して繰り返す、検出手段と、最後の反復における第Dの最尤検出器の出力に基づいて、前記スパース信号ベクトル内の原シンボルを推定するための推定手段とを備える、請求項8に記載の装置。第dの次元について、前記検出手段内の前記第dの最尤検出器が、前記スパース信号ベクトル内の前記原シンボルについての事後情報を生成するために、第dの次元の測定シンボルと第dの次元における先行情報とに基づいて、最尤検出を実行するために使用され、第dの次元において生成される前記事後情報が、第modd,D1の次元における先行情報を更新するために使用される、請求項9に記載の装置。第dの次元における事後情報pdxi=Xqが、第modd,D1の次元における先行情報を、以下の式によって更新するために使用され、ここで、emodd,D1xi=Xqは、先行する反復の第modd,D1の次元において生成され、これは、q=0~Q-1の場合、第modd,D1の次元におけるxiがXqである外部確率を表し、emodd,D1xi=Xqは、第1の反復において1に初期化され、後続する反復においてのように更新される、請求項10に記載の装置。前記スパース信号が、アナログスパース信号である場合、前記回復手段が、d=1~D、j=1~Jの場合に、内の各要素について、が0に等しいかどうかを判断するための判断手段であって、が、と初期化され、が、の第dの次元内の第jの要素であり、が0に等しい場合、l=1~Lとして、と設定し、ここで、Πdiは、第dの置換結果におけるxiのインデックスであり、は、Πdiの逆操作であり、i=1~Nの場合に、前記スパース信号ベクトルx内の各原シンボルxiについて、以下の式が満たされるかどうかを判断し、上記の式がdm,dnのペアについて満たされる場合、と設定し、ここで、およびである、判断手段と、回復されたスパース信号を、以下の式によって、測定ベクトルyから減算することによって、を更新するための更新手段であって、ここで、は、未回復シンボルが0に設定された、回復されたスパース信号ベクトルを表し、前記判断手段が、所定の条件が満たされるまで、上記の判断を複数回反復して繰り返す、更新手段とを備える、請求項8に記載の装置。前記所定の条件が、以下のいずれか、すなわち、-一定の反復回数に達したこと、-2つの連続する反復において生成された事後確率の間の差が事前定義された閾値を下回ったことを含む、請求項9に記載の装置。前記所定の条件が、以下のいずれか、すなわち、-一定の反復回数に達したこと、-前記スパース信号ベクトル内のすべての原シンボルの回復に成功したこと、-、ここで、およびは、1つの反復の前後のを表すことを含む、請求項12に記載の装置。上述の2つの問題により良く対処するため、2つの技術的ソリューションが提供され、一方は、スパース信号のデジタル性を十分に利用できる、新しい圧縮センシング技法を提供することであり、他方は、スパースな測定行列を用いて線形復号複雑度とスケッチ長の下限とを経験的に同時に達成できる、新しい圧縮センシング技法を提供することである。それらに基づいて、本発明の第1の態様では、デジタルスパース信号を処理するための方法が提供される。方法は、長さMの測定ベクトルyを獲得するために、M×N測定行列Aを用いて、長さNのスパース信号ベクトルx={xi}に対して線形測定linearmeasurementを実行するステップであって、測定行列Aが、によって表される、ステップを含み、ここで、d=1~Dである、ΑdΠdは、測定行列Aの部分行列であり、Πdは、N×Nランダム置換行列randompermutationmatrixであり、Αdは、によって表されるJ×N行列であり、ここで、M<<N、J×L=Nであり、スパース信号ベクトルx内の各成分xiは、有限集合Q={X0=0,X1,...,XQ-1}から取られ、q=1~Q-1の場合、Xqはゼロ以外の数であり、Qは集合のサイズであり、同じ置換行列から生成された測定シンボルは、1つの次元と呼ばれ、Dは、総次元数である。有利には、方法は、D個の次元に対してそれぞれ最尤検出を実行するために、D個の最尤検出器を使用するステップであって、第dの最尤検出器が、第dの次元に対して最尤検出を実行するために使用される、ステップと、所定の条件が満たされるまで、上記のステップを複数回反復して繰り返すステップと、最後の反復における第Dの最尤検出器の出力に基づいて、スパース信号ベクトル内の原シンボルを推定するステップとをさらに含むことができる。本発明の第1の態様における測定行列Aは、各次元におけるシンプルな最尤検出を可能にし、この最尤検出は、スパース信号のデジタル性を十分に利用し、次元ごとに計算量的に実現可能な局所最適な検出を提供する。測定行列の多次元構造は、準大域最適な推定結果を取得するために、次元間での反復的な情報交換を可能にする。さらに、本発明の第1の態様における測定行列Aは、スパースであり、すなわち、各列に非ゼロ成分よりもはるかに多くのゼロ成分を含む。測定行列のスパース性は、符号化と回復の両方において計算複雑度が低いこと、信号を漸進的に更新することが容易であること、およびストレージ要件が低いことなど、いくつかの魅力的な特性を有する。これらの利点は、本発明の第1の態様における技術的ソリューションを、スパースなデジタル信号を用いる圧縮センシングに対する有望で実用的なソリューションにする。本発明の第2の態様では、アナログスパース信号を処理するための方法が提供される。方法は、長さMの測定ベクトルyを獲得するために、M×N測定行列Aを用いて、長さNのKスパース信号ベクトルxに対して線形測定を実行するステップであって、測定行列Aが、によって表される、ステップを含み、ここで、d=1~Dである、ΑdΠdは、測定行列Aの部分行列であり、Πdは、N×Nランダム置換行列であり、Αdは、によって表されるJ×N行列であり、ここで、K<<N、M<<N、J×L=Nであり、スパース信号ベクトルxは、x={xi}∈RNであり、同じ置換行列から生成された測定シンボルは、1つの次元と呼ばれ、Dは、総次元数である。有利には、方法は、i.d=1~D、j=1~Jである、内の各要素について、が0に等しいかどうかを判断するステップであって、が、と初期化され、が、の第dの次元内の第jの要素である、ステップと、ii.が0に等しい場合、l=1~Lとして、と設定するステップであって、ここで、Πdiは、第dの置換結果におけるxiのインデックスであり、は、Πdiの逆操作である、ステップとをさらに含むことができ、方法は、u.i=1~Nである、スパース信号ベクトルx内の各原シンボルxiについて、以下の式が満たされるかどうかを判断するステップと、v.上記の式がdm,dnのペアについて満たされる場合、と設定するステップであって、ここで、およびである、ステップとをさらに含み、上記のステップの後、方法は、p.回復されたスパース信号を、以下の式によって、測定ベクトルyから減算することによって、を更新するステップであって、ここで、は、未回復シンボルが0に設定された、回復されたスパース信号ベクトルを表す、ステップと、q.所定の条件が満たされるまで、上記のステップを複数回反復して繰り返すステップとをさらに含む。本発明の第2の態様における測定行列Aの特殊な構造は、後で説明するような、測定シンボルのいくつかの興味深い特徴をもたらし、各反復における非常にシンプルな回復アルゴリズムを設計するために、その特徴を利用することができる。原信号を段階的に回復するために、反復プロセスが使用され、回復がより容易なシンボルから開始し、他のシンボルの回復が容易になるように、すでに回復されたシンボルの寄与を除去していく。そのような検出および除去操作を繰り返すことによって、準大域最適な解を獲得することができる。必要とされる複雑度は、原信号長Nにつれて線形に増加するにすぎない。多次元構造とランダム置換行列は、各測定値が、すべての原シンボルに対する何らかの有益な情報を直接的または間接的に統計的に提供することを保証し、この情報は、提案する技法の良好な性能にとって極めて重要である。さらに、本発明の第2の態様における技術的ソリューションは、経験的なスケッチ長の下限と線形複雑度とを同時に達成することができる。良好な経験的性能と低い複雑度は、本発明の第2の態様における技術的ソリューションを、スパースな測定行列を用いる圧縮センシングに対する良好で実用的な代替ソリューションにする。加えて、本発明の一実施形態によれば、スパース信号を測定および回復するための装置が提供され、装置は、長さMの測定ベクトルyを獲得するために、M×N測定行列Aを用いて、長さNのスパース信号ベクトルx={xi}に対して線形測定を実行するための測定手段であって、測定行列Aが、によって表され、ここで、d=1~Dである、ΑdΠdは、測定行列Aの部分行列であり、Πdは、N×Nランダム置換行列であり、Αdは、によって表されるJ×N行列であり、ここで、M<<N、J×L=Nであり、同じ置換行列から生成された測定シンボルは、1つの次元と呼ばれ、Dは、総次元数である、測定手段と、長さNのスパース信号ベクトルx={xi}を長さMの測定ベクトルyから回復するための回復手段とを備える。本発明が、添付の図面を参照しながら、例によって、さらに詳細に説明される。上記の図面全体において、同様の参照番号は、同様の、類似の、または対応する特徴または機能を指示することが理解されよう。これ以降本明細書において、本発明の上記の第1の態様の技術的ソリューションと、本発明の上記の第2の態様の技術的ソリューションが、それぞれ非常に詳細に説明される。図1は、一実施形態による、デジタルスパース信号の処理についてのフローチャートを示している。ステップS11において、長さMの測定ベクトルyを獲得するために、M×N測定行列Aを用いて、長さNのデジタルスパース信号ベクトルxに対して線形測定すなわち符号化が実行され、ここで、M<<Nである。独立した一様分布するi.i.d:independentandidenticallydistributed成分を有するデジタルスパース信号ベクトルx={xi}を考える。スパース信号ベクトルx内の各成分xiの値は、有限集合Q={X0=0,X1,...,XQ-1}から取られ、q=1~Q-1の場合、Xqはゼロ以外の数字であり、Qは集合のサイズである。各成分xiは、0である確率がp0であり、Xqである確率がpqq=1~Q-1であると仮定する。xはスパースであるので、である。圧縮センシングの理論に基づいて、xは、以下のような測定ベクトルyから回復することができ、y=Axn1ここで、nは、ゼロ平均を有し、E|n|2≦Mσ2である、長さMの雑音ベクトルである。この実施形態では、測定行列Aは、以下のように設計され、ここで、AdΠdd=1~Dは、測定行列Aの部分行列であり、Πdは、N×Nランダム置換行列であり、Adは、以下のように設計されるJ×N行列であり、ここで、J×L=Nであり、同じ置換行列から生成される測定シンボルは、1つの次元と呼ばれ、Dは、総次元数である。置換行列{Πd}は、D個の次元ごとに独立かつランダムに生成される。{Ad}内の非ゼロ成分は、ガウス確率変数である。符号化プロセスは、以下のように実施することができる。デジタルスパース信号ベクトルx内の原シンボルは、D回、独立して置換される。各回の置換結果は、J=N/L個のグループに分割され、各グループは、L個のシンボルを含む。第dの置換結果の第jのグループ内のシンボルは、Adの第j行内の対応する非ゼロ成分によって重み付けされた後、線形に重ね合わされて、この次元における第jの測定シンボルを生成する。全測定値の数Mは、グループ長L、次元数D、および信号長Nによって、M=ND/Lのように決定される。符号化の後、測定シンボルをデジタル化するために、量子化プロセスが適用される。量子化誤差は、式1の雑音ベクトルnによって表される。Sが、量子化レベルの数を表すとし、pquansが、測定シンボルがレベルSに量子化される確率を表すとする。その場合、1つの量子化された測定値を表すのに必要なビットの数は、である。したがって、xを表すのに必要なビットの総数は、B=bM=bND/Lであり、原シンボル当たり必要なビットの平均数は、である。原シンボル当たりの平均ビット数は、D、L、およびSの選択を介して調整することができる。式3における{Ad}の構造は、各次元において、L個のシンボルからなる各グループに対して、最尤検出MLを使用することを可能にする。Lに小さな値を選択することによって、ML検出の計算複雑度を制御することができる。ML検出は、原信号のデジタル性を十分に利用することができ、各次元ごとに、局所最適解を提供することができる。多次元構造は、準大域最適推定を達成するために、次元間での反復的な情報交換を可能にする。異なる次元における独立したランダム置換行列は、1つの次元における異なる測定値に寄与するシンボルは一緒にグループ化でき、他の次元における同じ測定値にも寄与できるので、統計的に、各測定値が、デジタルスパース信号ベクトルx内のすべてのシンボルに対する何らかの有益な情報を直接的または間接的に提供できることを保証する。これは、1つの測定値によって提供される、それに関連するL個のシンボルに対する情報は、これらのL個のシンボルが他の次元における他のシンボルとグループ化される場合、他のシンボルの検出に役立ち得ることを意味する。そのような特性は、提案する技法の耐雑音能力を大きく向上させるために、反復的な回復アルゴリズムにおいて十分に利用される。それに基づいて、ステップS12において、D個の次元に対してそれぞれ最尤検出を実行するために、D個の最尤検出器が使用される。すなわち、各最尤検出器は、図2に示されるように、1つの次元の検出を担当する。図2は、反復的なアルゴリズムの原理を示しており、DET-dは、第dの次元のローカル検出器であり、Tは、1つの反復の遅延を表し、/は、除法演算を表す。各ローカル検出器内で、L個のシンボルからなる各グループに対して、それらの雑音測定シンボルと事前情報とに基づいて、ML検出が実行される。各検出器の出力は、デジタルスパース信号ベクトルx内の原シンボルの事後情報であり、それは、次の反復において、他の次元における局所検出を精緻化するために使用される。図2に含まれる変数は、以下のように定義される。:第dの次元において、xiがXqq=0~Q-1である事前確率aprioriprobability。pdxi=Xq:第dの次元において、xiがXqq=0~Q-1である事後確率aposterioriprobability。edxi=Xq:第dの次元において、xiがXqq=0~Q-1である外部確率extrinsicprobability。事前確率は、第1の反復において、i=1~N、q=0~Q-1に対して、のように初期化され、外部確率は、第1の反復において、∀dに対して、edxi=Xq=1のように初期化される。によって表される、第dの次元における特定の測定値jについて考える。に寄与するL個の原シンボルのインデックスをとする。の値は、置換行列Πdによって決定される。これらL個のシンボルの事後確率は、ML検出を使用して、のように計算される。式6における総和は、第lの要素がXqに固定された、すべての可能なベクトルc∈QLを対象とする。外部確率は、事後確率から事前確率を抽出することによって計算される。第dの次元において生成された事後確率は、第modd,D1の次元における事前確率を、のように更新するために使用される。emodd,D1xi=Xqは、先行する反復における第modd,D1の次元において生成されるので、循環して再び第modd,D1の次元に戻ることがないようにすべきであり、これは反復的な検出の基本規則であることに留意されたい。これは、式8における除法演算によって実現される。その後、ステップS13において、上述の手順を、所定の条件が満たされるまで、複数回反復して繰り返す。所定の条件は、例えば、以下のいずれかを含むことができる。-一定の反復回数に達した。-2つの連続する反復において第Dの最尤検出器において生成された事後確率の間の差が事前定義された閾値を下回った。最後に、ステップS14において、デジタルスパース信号ベクトルx内の原シンボル{xi}が、最後の反復における第Dの最尤検出器の出力に基づいて推定される。例えば、原シンボル{xi}に対して、以下のような硬判定harddecisionが行われる。ここで、である。この実施形態における上で提案した反復アルゴリズムの複雑度は、ONDQL/Lであり、これは、LがNよりもはるかに小さく、Nとともに大きくならないので、最適なソリューションの複雑度OQNよりもはるかに低い。Dが一定である場合、Lが小さくなるほど、測定値数Mは多くなることに留意されたい。そのため、DとLの値を調整することによって、計算複雑度と測定値数の間の異なるトレードオフを達成することができる。以下の説明では、上で提案した技術的ソリューションの性能を、数値結果を使用して説明する。xi∈{0,1}である、デジタルスパース信号ベクトルx内の2進原信号を考える。xの成分は、01である確率がp0p1であり、p0>>p1である、独立した一様分布する変数である。ゼロ平均および単位分散を有する、独立した一様分布するガウス確率変数である、非ゼロ成分を有する、測定行列Aが、式2および3に従って生成される。測定行列Aは、各行が単位ノルムを有するように正規化される。量子化レベルは、S=5に固定され、以下の量子化規則が用いられ、ここで、Quanxは、量子化後のxの値を表す。デジタルスパース信号ベクトルxを用いる場合、量子化前の式2および3において定義された測定行列Aを使用して生成される線形測定シンボルは、0である確率が大きいことに留意されたい。ゼロ測定シンボルが出現した場合、それに関連するL個の原シンボルはすべてゼロであると高い精度で結論を下すことができ、これは、反復的な回復アルゴリズムにおける他の原シンボルの検出に非常に役立つ。したがって、0を他の値から区別するために、式20における0のために特定の量子化レベルが使用される。確率{Pquans,s=1~5}を獲得するためにモンテカルロシミュレーションを使用し、式5に従って、原シンボル当たり必要なビットの平均数ηを計算する。図3aおよび図3bは、上で提案した技術的ソリューションと、ランダムガウスセンシング行列、ラッソアルゴリズムLassoalgorithm、およびベイズフレームワークにそれぞれ基づいた、2つの従来技法との間の速度-歪み性能の比較を示している。可逆回復の場合に原シンボル当たり必要なビットの最小数も、参考のために示されている。ここでは、p1=0.1および0.05に設定し、反復回数は5に固定する。確率{Pquans}が、表1に挙げられている。表1から、原シンボル当たり必要なビットの数ηを計算することができる。0.14から1までのηの異なる値を獲得するために、Dを1から4まで、Lを10から12までの間で調整する。ξによって表される歪みは、以下のように測定され、それは、Nによって正規化された内の不正確な成分の平均数に等しい。参考のため、エントロピ符号化を介する可逆圧縮の場合に原シンボル当たり必要なビットの最小数が、図3に示されている。2つの従来手法の速度-歪み性能も含まれており、2つの従来手法は、ランダムガウスセンシング行列に基づき、信号回復のために、凸緩和詳細については、[R.Gribonval、M.Nielsen、Highlysparserepresentationsfromdictionariesareuniqueandindependentofthesparsenessmeasure、AalborgUniv.、Aalborg、Denmark、Tech.Rep.、2003年10月]および[J.A.Tropp、Justrelax:Convexprogrammingmethodsforidentifyingsparsesignalsinnoise、IEEETrans.Inf.Theory、vol.52、no.3、1030~1051頁、2006年3月]を参照されたいと、ベイズフレームワーク詳細については、[S.Ji、Y.Xue、L.Carin、Bayesiancompressivesensing、IEEETrans.SignalProcessing、vol.56、no.6、2346~2356頁、2008年6月]および[M.E.Tipping、SparseBayesianlearningandtherelevancevectormachine、JournalofMachineLearningResearch、vol.1、211~244頁、2001年9月]を参照されたいとをそれぞれ利用する。凸緩和の場合、ラッソアルゴリズム詳細については、[M.J.Wainwright、Sharpthresholdsforhigh-dimensionalandnoisysparsityrecoveryusing11-constrainedquadraticprogrammingLasso、IEEETrans,onInform.Theory、vol.55、2183~2202頁、2009年5月]および[R.Tibshirani、Regressionshrinkageandselectionviathelasso、JournaloftheRoyalStatisticalSociety、SeriesB、267~288頁、1996年]を参照されたいを使用する。ベイズフレームワークに基づいたアルゴリズムの場合、論文S.Ji、Y.Xue、L.Carin、Bayesiancompressivesensing、IEEETrans.SignalProcessing、vol.56,no.6、2346~2356頁、2008年6月に紹介された技法が使用される。このケースでは、各測定値が0になる可能性は非常に低いので、0専用の量子化レベルを除去したことを除いて、従来手法はどちらも、式11と同様の量子化規則を使用する。従来手法の場合の確率{pquans,s=1~5}も、表1に挙げられている。図3から、提案した技法は、ランダムセンシング行列と凸緩和/ベイズフレームワークとに基づいた従来手法よりもはるかに良好な速度-歪み性能を達成できることが観測される。図4は、別の実施形態による、アナログスパース信号の処理についてのフローチャートを示している。ステップS41において、長さMの測定ベクトルyを獲得するために、M×N測定行列Aを用いて、長さNのKスパース信号ベクトルxに対して線形測定すなわち符号化が実行され、ここで、K<<N、M<<Nであり、Kスパース信号ベクトルは、x={xi}∈RNであり、測定ベクトルは、y∈RMである。圧縮センシングの理論によれば、xは、以下のような測定ベクトルyから回復することができる。y=Ax13この実施形態では、測定行列Aは、以下のように設計され、ここで、AdΠdd=1~Dは、測定行列Aの部分行列であり、Πdは、N×Nランダム置換行列であり、Adは、以下のように設計されるJ×N行列であり、ここで、J×L=Nであり、同じ置換行列から生成される測定シンボルは、1つの次元と呼ばれ、Dは、総次元数である。明らかに、このようにして生成された測定行列Aは、スパースであり、列当たりD個の非ゼロ成分を有するにすぎない。符号化操作は、以下のように実施することができる。デジタルスパース信号ベクトルx内の原シンボルは、D回、独立して置換される。各回の置換結果は、J=N/L個のグループに分割され、各グループは、L個のシンボルを含む。第dの置換結果の第jのグループ内のシンボルは、Adの第j行内の対応する非ゼロ成分によって重み付けされた後、線形に重ね合わされて、この次元における第jの測定を生成する。によって、第dの次元における第jの測定シンボルを表し、それは、となり、ここで、は、xの第dの置換結果である。Πdiを、第dの置換結果におけるxiのインデックスとし、は、その逆操作であり、となる。スパース信号ベクトルx内のどの原シンボルxiにも、1つの次元内から1つずつ、D個の測定値が関連付けられる。総測定値数すなわちスケッチ長Mは、グループ長L、次元数D、および原信号長Nによって、M=ND/Lのように決定される。式16から、測定行列Aは、各列内にD個の非ゼロ要素を有するにすぎないことが分かる。xの非ゼロ要素だけが、符号化における加法および乗法演算に成立させることにも留意されたい。したがって、提案した技法の符号化複雑度は、DK個の乗算およびDK個の加算についてのものである。式15における{Ad}のブロック対角構造と、D個の次元におけるランダム置換行列は、測定シンボルの以下の特徴をもたらし、それは、信号回復において非常に役立つ。説明に便利なように、測定シンボルの次数degreeを、測定シンボルに関連付けられた非ゼロ原シンボルの数として定義する。16から、各測定シンボルは、L個の原シンボルに関連付けられるにすぎないことが分かり、したがって、以下の2つの事態が、比較的大きな確率で発生することを検証することは容易である。事態1:測定シンボルが次数0を有する。事態2:非ゼロ原シンボルの場合、それに関連付けられた少なくとも2つの測定値が次数1を有するD≧2を仮定する。上記の2つの事態の確率は、以下のように計算することができる。p1=K/N、p0=1-p1とする。p1およびp0は、原シンボルが非ゼロおよびゼロである確率をそれぞれ表す。その場合、事態1および事態2の確率は、およびのように近似的に計算することができる。K<<Nである場合、LおよびDに適切な値を選択することによって、2つの確率を比較的大きくできることが容易に分かる。例えば、K=100、N=1000、L=10、D=4である場合、Pissue-1=34.87、Pissue-2=50.29である。事態1の場合、測定シンボルは、ゼロである。測定シンボルが、2つ以上の非ゼロ原シンボルに関連付けられる場合、これらの非ゼロシンボルが、互いに完全に相殺し合う可能性は非常に低く式16を参照、そのため、測定シンボルは、1に近い、非ゼロである確率を有することも留意されたい。したがって、ゼロの測定シンボルが現れた場合、それに関連付けられたすべての原シンボルはゼロであると推測することができる。事態2の場合、非ゼロ原シンボルの2つの次数1の測定値は、以下のような関係にある。非ゼロ原シンボルxiが、2つの次数1の測定値を次元d1およびd2において有すると仮定する。m=1および2に対して、およびとする。これら2つの次数1の測定値の値は、以下の関係を有する。明らかに、xiの値は、式20から計算することができる。事態1および2についての上述の説明に基づいて、次にステップS42において、内の各要素d=1~D、j=1~Jについて、が0に等しいかどうかを判断し、が0に等しい場合、l=1~Lとして、と設定し、ここで、は、のように初期化され、i=1~Nである、スパース信号ベクトルx内の各原シンボルxiに対して、以下の式が満たされるかどうかが判断され、上記の式がdm,dnのペアについて満たされる場合、と設定する。次にステップS43において、回復されたスパース信号を、以下の式によって、測定ベクトルyから減算することによって、が更新され、ここで、は、未回復のシンボルが0に設定された、回復されたスパース信号ベクトルを表す。そのような干渉除去操作は、2つの方法で、他のシンボルの回復に役立つ。第1に、測定シンボルに関連付けられた原シンボルが、1つを除いてすべて回復された場合、未回復の原シンボルだけを干渉除去後に測定値から直接的に推定することができる。第2に、非ゼロ原シンボルが、yから減算される場合、それに関連付けられた測定値の次数が、1だけ減らされる。これによって、事態1および2の新しいケースをにおいて導入することができるので、上記の2つの規則を再び適用して、からより多くの原シンボルを再生成することができる。これが、再帰的にxを回復するために、干渉除去とともに反復的なプロセスを使用する動機になる。次にステップS44において、上述のステップS42およびS43が、所定の条件が満たされるまで、複数回反復して繰り返される。所定の条件は、例えば、以下のいずれかを含むことができる。-一定の反復回数に達した。-スパース信号ベクトル内のすべての原シンボルの回復に成功した。-、ここで、およびは、1つの反復の前後のを表す。この実施形態における上で提案した反復アルゴリズムの複雑度は、ONである。以下の説明では、上で提案した技術的ソリューションの性能が、数値結果を使用して説明される。非ゼロ要素としてガウス確率変数を有するスパース原信号xを考える。非ゼロ成分としてガウス確率変数を有する測定行列Aが、式14および15に従って生成される。シミュレーションでは、p1=K/N=0.1および0.05に設定され、次元数はD=4である。異なるスケッチ長Mが得られるように、グループ長Lが調整される。反復的な回復プロセスは、以下の3つの条件のいずれか1つが満たされた場合に終了する。aT=20回の反復に達した、bすべての原シンボルの回復に成功した、c、ここで、およびは、1つの反復の前後のの結果である。平均反復回数は、M/Nに応じて、Tave=6~10である。図5は、測定値数MとKlog2N/Kの間の関係を示している。この図の目的は、提案した技法がスケッチ長の下限OKlog2N/Kを達成できることを示すことである。図5には、上で提案した技術的ソリューションの場合、必要とされる測定値の数Mが信号長Nとともに線形に増加することが示されている。ここで、Nを1000から10000までに設定し、回復失敗確率が高々0.01であることを保証するようにMを選択する。回復失敗は、である場合に発生し、ここで、は、最後の反復後のを表すことに留意されたい。図5は、提案した技術的ソリューションが、αが約0.6~0.8の非常に小さな値を取る場合に、αKlog2N/Kのスケッチ長下限を経験的に達成できることを明らかに示している。図6aおよび図6bは、上で提案した技術的ソリューションの場合の、回復失敗確率とαすなわちスケッチ長の間の関係を示している。ここで、N=4000は、一定であり、αは、0.5~1.2の間で変化する。比較のため、図6には、l1マジックl1magicとベイズフレームワークとに基づいた既存の回復アルゴリズムの場合の、回復失敗確率も示されている。見て分かるように、同じ回復精度を達成するのに、上で提案した技術的ソリューションは、l1マジックおよびベイズフレームワークよりもはるかに少ない測定値しか必要としない。そのような良好なスケッチ長は、線形複雑度を有するように達成される。良好な経験的性能および線形回復複雑度は、提案する技法を、スパースな行列を用いる圧縮センシングに対する有望で魅力的なソリューションにする。上では、本発明の技術的ソリューションを方法の観点から説明したが、これ以降では、本発明の技術的ソリューションを装置の観点からさらに説明する。本発明の一実施形態によれば、スパース信号を測定および回復するための装置がさらに提供される。装置は、長さMの測定ベクトルyを獲得するために、M×N測定行列Aを用いて、長さNのスパース信号ベクトルx={xi}に対して線形測定を実行するための測定手段であって、測定行列Aが、によって表され、ここで、d=1~Dである、AdΠd、測定行列Aの部分行列であり、Πdは、N×Nランダム置換行列であり、Adは、によって表されるJ×N行列であり、ここで、M<<N、J×L=Nであり、同じ置換行列から生成される測定シンボルは、1つの次元と呼ばれ、Dは、総次元数である、測定手段と、長さNのスパース信号ベクトルx={xi}を長さMの測定ベクトルyから回復するための回復手段とを備える。有利には、スパース信号がデジタルスパース信号であり、スパース信号ベクトルx内の各成分xiが有限集合Q={X0=0,X1,...,XQ-1}から取られ、q=1~Q-1の場合のXqがゼロ以外の数字であり、Qが集合のサイズである場合、回復手段は、D個の次元に対して最尤検出をそれぞれ実行するためのD個の最尤検出器を含む検出手段であって、第dの最尤検出器が、第dの次元に対する最尤検出を実行するために使用され、検出手段が、所定の条件が満たされるまで、上記の検出を複数回反復して繰り返す、検出手段と、最後の反復における第Dの最尤検出器の出力に基づいて、スパース信号ベクトル内の原シンボルを推定するための推定手段とをさらに備える。具体的には、第dの次元について、検出手段内の第dの最尤検出器が、スパース信号ベクトル内の原シンボルの事後情報を生成するために、第dの次元の測定シンボルと第dの次元における先行情報とに基づいて、最尤検出を実行するために使用され、第dの次元において生成される事後情報が、第modd,D1の次元における先行情報を更新するために使用される。好ましくは、第dの次元における事後情報pdxi=Xqが、第modd,D1の次元における先行情報を、以下の式によって更新するために使用され、ここで、emodd,D1xi=Xqは、先行する反復の第modd,D1の次元において生成され、これは、q=0~Q-1の場合、第modd,D1の次元におけるxiがXqである外部確率を表し、emodd,D1xi=Xqは、第1の反復において1に初期化され、である。所定の条件は、例えば、以下のいずれかを含むことができる。-一定の反復回数に達した。-2つの連続する反復において第Dの最尤検出器において生成された事後確率の間の差が事前定義された閾値を下回った。有利には、スパース信号がアナログスパース信号である場合、回復手段は、d=1~D、j=1~Jの場合、内の各要素について、が0に等しいかどうかを判断するための判断手段であって、が、と初期化され、が0に等しい場合、l=1~Lとして、と設定し、ここで、Πdiは、第dの置換結果におけるxiのインデックスであり、は、Πdiの逆操作であり、i=1~Nである、スパース信号ベクトルx内の各原シンボルxiに対して、以下の式が満たされるかどうかを判断し、dm,dnのペアについて満たされる場合、と設定し、ここで、およびである、判断手段と、回復されたスパース信号を、以下の式によって、測定ベクトルyから減算することによって、を更新するための更新手段であって、ここで、は、未回復のシンボルが0に設定された、回復されたスパース信号ベクトルを表し、判断手段が、所定の条件が満たされるまで、上述の判断を複数回反復して繰り返す、更新手段とをさらに備えてもよい。所定の条件は、例えば、以下のいずれかを含むことができる。-一定の反復回数に達した。-スパース信号ベクトル内のすべての原シンボルの回復に成功した。-、ここで、およびは、1つの反復の前後のを表す。上で説明した実施形態は、本発明を限定するためではなく、説明するために与えられたことに留意されたく、また当業者が容易に理解するように、本発明の主旨および範囲から逸脱することなく、変更および変形を施すことができることを理解されたい。そのような変更および変形は、本発明および添付の特許請求の範囲内にあると見なされる。本発明の保護範囲は、添付の特許請求の範囲によって確定される。加えて、特許請求の範囲内の参照番号はいずれも、特許請求の範囲に対する限定と解釈すべきではない。動詞comprise含む、備えるおよびその活用形の使用は、請求項内で述べられた要素またはステップ以外の要素またはステップの存在を排除するものではない。要素またはステップの前に置かれる不定冠詞aまたはanは、複数のそのような要素またはステップの存在を排除するものではない。"