どうすれば3Dで低差異点の自由形式のシーケンスを生成できますか?

3
Paul B. Slater 2017-04-12 22:02.

3D超立方体上の点の不一致の少ないシーケンスが欲しい $[-1,1]^3$、ただし、固定数にコミットする必要はありません $n$ 事前にポイントの数を確認します。これは、数値積分の推定値が、低差異ポイントの数が増えるにつれてどのように発展するかを示しています。

結果が修正された場合は、最初からやり直す必要はありません。 $n$物足りないです。もちろん、乱数を使用することもできますが、そうすると収束動作が悪くなります。

「相関のないランダムポイントよりも均一にn空間を埋めるnタプルのシーケンス。これは、低不一致シーケンスとも呼ばれます。通常の均一ランダム数と準ランダムシーケンスはどちらも均一に分布したシーケンスを生成しますが、二。" (mathworld.wolfram.com/QuasirandomSequence.html)

この質問は、mathematica.stack.exchange(https://mathematica.stackexchange.com/questions/143457/how-can-one-generate-an-open-ended-sequence-of-low-discrepancy-points-in-3d)

以下の彼の回答では、マーティン・ロバーツがオープンエンドの一様分布列の問題に対して非常に興味深く魅力的なアプローチを進めているので、私が報告したばかりの彼のアプローチの(継続的な)実装を示したいと思います。 https://arxiv.org/abs/1809.09040。秒で。XI(p。19)および図 そこで5と6で、2つの問題を分析します。1つはサンプリング次元に関するものです。$d=36$ と1つ $d=64$-両方ともパラメータを使用します $\bf{\alpha}_0$ 0に設定し、また $\frac{1}{2}$。ロバーツのアルゴリズムによって生成された準均一に分布した点を準均一に分布した正規変量に変換するために、ヘンリック・シューマッハが次のように答えたときに開発したコードを使用します。https://mathematica.stackexchange.com/questions/181099/can-i-use-compile-to-speed-up-inversecdf

3 answers

2
Martin Roberts 2018-07-09 19:11.

OPがMathstackexchangeからこの質問をクロスポストしたので、私はそこに書いた回答もクロスポストしました。

に対する最も単純な従来のソリューション $d$3次元で非常に良い結果を提供する次元は、最初の3つの素数(2、3、5)に基づくハルトン列を使用することです。ハルトン列は、1次元のファンデルコルプト数列を一般化したものであり、3つのパラメーターが互いに素である必要があるだけです。詳細については、ウィキペディアの記事「ハルトン列」を参照してください。

使用できる代替シーケンスは、Weyl / Kroneckerシーケンスの一般化です。このシーケンスも通常、最初の3つの素数を使用しますが、この場合、これらの数の平方根が無理数であるという理由だけで選択されます。

ただし、最近、詳細なブログ投稿「準乱数列の不合理な有効性」を、任意の次元で自由形式の一様分布列を簡単に作成する方法について書いています。

  • 代数的に単純
  • 計算が速く
  • より一貫性のある出力を生成します
  • 技術的な問題が少ない

HaltonやKroneckerシーケンスなど、既存の既存の低差異シーケンスよりも。

解は、黄金比に依存する解を持つ1次元問題を一般化する加法漸化式(モジュロ1)です。の解決策$d$-次元の問題、特別な定数に依存 $\phi_d$、 どこ $\phi_d$ のユニークな正のルートです $x^{d+1}=x+1$

ために $d=1$、  $ \phi_1 = 1.618033989... $、これは正規の黄金比です。

ために $d=2$$ \phi_2 = 1.3247179572... $、プラスチック定数と呼ばれることが多く、いくつかの美しい特性があります。この値は、関連する2次元問題の最適値である可能性が最も高いと推測されました[Hensley、2002]。Jacob Rusは、この2次元の低不一致シーケンスの美しい視覚化を投稿しました。これは、ここにあります。

そして最後に、特にあなたの質問に関連して、 $d=3$$ \phi_3 = 1.2207440846... $

この特別な定数を手にすると、 $n$-第3項は、計算が非常に簡単で高速になりました。

$$ R: \mathbf{t}_n = \pmb{\alpha}_0 + n \pmb{\alpha} \; (\textrm{mod} \; 1),  \quad n=1,2,3,... $$ $$ \textrm{where} \quad \pmb{\alpha} =(\frac{1}{\phi_d}, \frac{1}{\phi_d^2},\frac{1}{\phi_d^3},...\frac{1}{\phi_d^d}), $$

もちろん、これが漸化式と呼ばれる理由は、上記の定義が $$ R: \mathbf{t}_{n+1} = \mathbf{t}_{n} + \pmb{\alpha} \; (\textrm{mod} \; 1) $$

ほとんどすべての場合、 $\pmb{\alpha}_0 $ 主要な特性を変更しないため、明らかな単純さの理由から、 $\pmb{\alpha}_0 =\pmb{0}$通常の選択です。ただし、対称性に関連して、次のことを示唆するいくつかの議論があります。$\pmb{\alpha}_0=\pmb{1/2}$ より良い選択です。

特に $d=3$$\phi_3 = 1.2207440846... $ などのために $\pmb{\alpha}_0= (1/2,1/2,1/2) $$$\pmb{\alpha} = (0.819173,0.671044,0.549700) $$ したがって、正規の3次元シーケンスの最初の5つの項は次のとおりです。

  1. (0.319173、0.171044、0.0497005)
  2. (0.138345、0.842087、0.599401)
  3. (0.957518、0.513131、0.149101)
  4. (0.77669、0.184174、0.698802)
  5. (0.595863、0.855218、0.248502)..。

もちろん、このシーケンスの範囲は[0,1]であるため、[-1,1]の範囲に変換するには、線形変換を適用するだけです。 $ x:= 2x-1 $。結果は

  1. (-0.361655、-0.657913、-0.900599)
  2. (-0.72331、0.684174、0.198802)
  3. (0.915035、0.0262616、-0.701797)
  4. (0.55338、-0.631651、0.397604)
  5. (0.191725、0.710436、-0.502995)、..。

このシーケンスを作成するためのMathematicaコードは次のとおりです。

f[n_] := x /. FindRoot[x^(1 + n) == x + 1, {x, 1}];

d = 3;
n = 5

gamma = 1/f[d];
alpha = Table[gamma^k , {k, Range[d]}]
ptsPhi =  Map[FractionalPart, Table[0.5 + i alpha, {i, Range[n]}], {2}]

同様のPythonコードは

# Use Newton-Rhapson-Method
def gamma(d):
    x=1.0000
    for i in range(20):
        x = x-(pow(x,d+1)-x-1)/((d+1)*pow(x,d)-1)
    return x

d=3
n=5

g = gamma(d)
alpha = np.zeros(d)                 
for j in range(d):
    alpha[j] = pow(1/g,j+1) %1
z = np.zeros((n, d))    
for i in range(n):
    z = (0.5 + alpha*(i+1)) %1

print(z)

お役に立てば幸いです。

0
user32038 2017-10-20 14:54.

オープンエンドシーケンスを取得するためのもう1つの優れたソリューションは、Haltonメソッドを使用することです。また、どの寸法でも非常に簡単に実装できます。d <8の場合、通常は良好な特性があり、これを超えると、通常、ハルトンよりもパフォーマンスが高くなります。

0
Paul B. Slater 2020-04-24 00:25.

元の質問は2017年4月に提起されました。今、数日前、私は質問を拡張しました

https://mathematica.stackexchange.com/questions/143457/how-can-one-generate-an-open-ended-sequence-of-low-discrepancy-points-in-3d

マーティン・ロバーツが元の質問への回答で与えたアルゴリズムによって生成された準ランダムな結果の信頼性(コマンドFractionalPartが各反復で適用されることに注意)に対する(Mathematica)WorkingPrecision設定の可能な関連性について懸念を表明する。

私のテスト例は、3Dコンテキストでの9つの値の推定に関するもので、そのうち4つは事前の検討からわかっています。(質問では、3つを述べましたが、4つ目も既知であることに気付きました。)4つの値は、準乱数手順が収束すると予想されます(を参照)。https://arxiv.org/abs/2004.06745)\ begin {equation} \ left \ {\ frac {1} {36}、\ frac {8 \ pi} {27 \ sqrt {3}}、\ frac {1} {81} \ left(27+ \ sqrt {3} \ log \ left(97 + 56 \ sqrt {3} \ right)\ right)、\ frac {2} {81} \ left(4 \ sqrt {3} \ pi -21 \ right)\ right \ } \ approx \ end {equation} \ begin {equation} \ {0.027777777777777777778,0.53742203384717565944、0.44597718463717723667、\ 0.018903515328657140917 \}。\ end {equation}見積もりでは、30億の3Dポイントを使用し、1億の間隔で結果を記録しました。定数/ターゲットライン1とともに、4セットの結果を示すプロットは次のとおりです。

黄色の曲線は、0.44597718463717723667の推定値に対応しています。0.02777777777777777777の推定値は、明らかに4つの中で最良であり、1の一定線の近くにあります。青い曲線は0.53742203384717565944に対応し、(最も変動の大きい)緑は最小の目標値0.018903515328657140917に対するものです。

これらの結果は、WorkingPrecision-> 20を使用して取得されました。

それから、私の懸念のために、私は計算の繰り返しを行いましたが、現在はWorkingPrecision-> 40を採用しています。7億回の反復後、結果はWorkingPrecision-> 20を使用して得られた結果と同じでした。(やや不思議なことに、計算時間は約$7\%$。)以前と同様に、30億回の反復を続けており、最初の結果セットからの逸脱を検出した場合は、この回答を更新します。また、30億を超えても差がなければ、それにも注意します。

しかし、現時点では、WorkingPrecisionの設定を20に設定することは、目前のタスクには確かに適切であったようです。

また、各準ランダム3Dポイント(Q1、Q2、Q3)が生成されるときに、それが制約\ begin {equation} \ text {Q1}> 0 \ land \ text {Q2}> 0を満たしているかどうかをテストすることにも注意してください。 \ land \ text {Q3}> 0 \ land \ text {Q1} +3 \ text {Q2} +2 \ text {Q3} <1。\ end {equation}そうでない場合は、それ以上の検討から破棄されます。のみ$\frac{1}{36} \approx 0.027777777777777777778$ 制約を満たす必要があります(そして、プロットが示すように、これは確かに当てはまります)。

更新:

現在、2セットの結果があります。どちらも30億回の反復に基づいており、最初はWorkingPrecision-> 20を使用し、2番目はWorkingPrecision-> 40を使用しています。

生成された各ポイント(Q1、Q2、Q3)について、上記のように、制約\ begin {equation} \ text {Q1}> 0 \ land \ text {Q2}> 0 \ land \を満たしているかどうかをテストしました。text {Q3}> 0 \ land \ text {Q1} +3 \ text {Q2} +2 \ text {Q3} <1。\ end {equation}どちらの場合も、ポイントの同じ数(83,333,308)がテストに合格し、0.0277777693333333の確率、つまり非常に近い値が得られました。$\frac{1}{36}$、単純な3D統合がもたらすこと。

次に、これらの83,333,308ポイントのそれぞれについて、さらに( "PPT"-"正の部分転置")制約を満たしているかどうかをテストしました\ begin {equation} \ text {Q1} ^ 2 + 3 \ text {Q1} \ text { Q2} +(3 \ text {Q2} + \ text {Q3})^ 2 <2 \ text {Q1} \ text {Q3} +3 \ text {Q2}。\ end {equation}

さて、さらなるテストに合格した2つのポイントは異なりましたが、ほぼ同じでした。WorkingPrecision-> 20の場合、その数は44,785,111であり、WorkingPrecision-> 40の場合、その数は2つ大きく、つまり44,785,113でした。(比率[$R_1$]後者の数と共通の数83,333,308の比率は、さらに[$R_2$]既知の値に $\frac{8 \pi }{27 \sqrt{3}} \approx 0.53742203384718$ 0.9999990427であり、以前の[より少ないWorkingPrecision]の数44,785,111よりも1に近い(期待/期待される)。)

これから、WorkingPrecisionの設定を高くして分析を続けます。

Related questions

MORE COOL STUFF

「水曜日」シーズン1の中心には大きなミステリーがあります

「水曜日」シーズン1の中心には大きなミステリーがあります

Netflixの「水曜日」は、典型的な10代のドラマ以上のものであり、実際、シーズン1にはその中心に大きなミステリーがあります.

一部のファンがハリー・スタイルズとオリビア・ワイルドの「非常に友好的な」休憩が永続的であることを望んでいる理由

一部のファンがハリー・スタイルズとオリビア・ワイルドの「非常に友好的な」休憩が永続的であることを望んでいる理由

一部のファンが、オリビア・ワイルドが彼女とハリー・スタイルズとの間の「難しい」が「非常に友好的」な分割を恒久的にすることを望んでいる理由を見つけてください.

エリザベス女王の死後、ケイト・ミドルトンはまだ「非常に困難な時期」を過ごしている、と王室の専門家が明らかにする 

エリザベス女王の死後、ケイト・ミドルトンはまだ「非常に困難な時期」を過ごしている、と王室の専門家が明らかにする&nbsp;

エリザベス女王の死後、ケイト・ミドルトンが舞台裏で「非常に困難な時期」を過ごしていたと伝えられている理由を調べてください.

ウィリアム王子は「非常に現代的なお父さん」だと王室の専門家は言う

ウィリアム王子は「非常に現代的なお父さん」だと王室の専門家は言う

ある王室の専門家が、特に彼の家族の他の王室の両親と比較して、ウィリアム王子が「非常に現代的な父親」であると考える理由を学びましょう.

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セント ヘレナ島のジェイコブズ ラダーは 699 段の真っ直ぐ上る階段で、頂上に到達すると証明書が発行されるほどの難易度です。

The Secrets of Airline Travel Quiz

The Secrets of Airline Travel Quiz

Air travel is far more than getting from point A to point B safely. How much do you know about the million little details that go into flying on airplanes?

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

バイオニック読書はあなたをより速く読むことができますか?

バイオニック読書はあなたをより速く読むことができますか?

BionicReadingアプリの人気が爆発的に高まっています。しかし、それは本当にあなたを速読術にすることができますか?

メイミー・ジョンソン、ニグロリーグでピッチングした女性、82歳で死去

メイミー・ジョンソン、ニグロリーグでピッチングした女性、82歳で死去

写真提供者:Khue Bui / AP Mamie Johnsonは、ニグロリーグでプレーする3人の女性の1人で、82歳で亡くなりました。ジョンソンは子供の頃から野球を始め、最初に全米女子プロ野球に挑戦しました。 17歳のリーグだが、黒人だったのでフィールドへの出場は許されなかった。

グローアップゴール:カルメンデラヴァラードは時代を超えた魅力の縮図です

グローアップゴール:カルメンデラヴァラードは時代を超えた魅力の縮図です

ジャックミッチェル/ゲッティイメージズ日曜日の夜、ダンサー、振付師、女優のカルメンデラヴァラードが第40回ケネディセンター名誉賞を受賞しました。今年は、ドナルドトランプ首長のクレチンが祝福されていないことで、この式典がさらに注目を集めました。まだ見事な86歳のとき、伝説的なパフォーマーであるde Lavalladeは失望せず、真の優雅さと美しさが時代を超えていることを示しました。

ファイナルファンタジーXVのマルチプレイヤーは少量でとても楽しいです

ファイナルファンタジーXVのマルチプレイヤーは少量でとても楽しいです

くそー、私はちょうどこのシャツを買いました。一部の人にとっては、ファイナルファンタジーXVのマルチプレイヤー拡張パックは、スクウェア・エニックスの壮大なRPGを友達と体験するための面白い(少しイライラする場合でも)方法です。

ナズは面会権をめぐってケリスを法廷に連れて行く

ナズは面会権をめぐってケリスを法廷に連れて行く

ナズとケリス(ローレンス・ルシエ/ゲッティイメージズ)ナズは息子とより多くの時間を過ごしたいと考えており、現在、元妻のケリスを正式な面会スケジュールのために法廷に連れて行っています。ブラストが入手した文書によると、ナズは彼がは「長年にわたってケリスと協力して働いてきた」が、ケリスは「彼女が自分にとって都合がよいと判断した場合にのみ、息子との監護権を行使することを許可している。

ケイト・ミドルトンとウィリアム王子は、彼らが子供たちと行っているスパイをテーマにした活動を共有しています

ケイト・ミドルトンとウィリアム王子は、彼らが子供たちと行っているスパイをテーマにした活動を共有しています

ケイト・ミドルトンとウィリアム王子は、子供向けのパズルの本の序文を書き、ジョージ王子、シャーロット王女、ルイ王子と一緒にテキストを読むと述べた.

事故で押しつぶされたスイカは、動物を喜ばせ水分補給するために野生生物保護団体に寄付されました

事故で押しつぶされたスイカは、動物を喜ばせ水分補給するために野生生物保護団体に寄付されました

Yak's Produce は、数十個のつぶれたメロンを野生動物のリハビリ専門家であるレスリー グリーンと彼女のルイジアナ州の救助施設で暮らす 42 匹の動物に寄付しました。

デミ・ロヴァートは、新しいミュージシャンのボーイフレンドと「幸せで健康的な関係」にあります: ソース

デミ・ロヴァートは、新しいミュージシャンのボーイフレンドと「幸せで健康的な関係」にあります: ソース

8 枚目のスタジオ アルバムのリリースに向けて準備を進めているデミ ロヴァートは、「スーパー グレート ガイ」と付き合っている、と情報筋は PEOPLE に確認しています。

Plathville の Kim と Olivia Plath が数年ぶりに言葉を交わすことへようこそ

Plathville の Kim と Olivia Plath が数年ぶりに言葉を交わすことへようこそ

イーサン プラスの誕生日のお祝いは、TLC のウェルカム トゥ プラスビルのシーズン 4 のフィナーレで、戦争中の母親のキム プラスと妻のオリビア プラスを結びつけました。

仕事の生産性を高める 8 つのシンプルなホーム オフィスのセットアップのアイデア

仕事の生産性を高める 8 つのシンプルなホーム オフィスのセットアップのアイデア

ホームオフィスのセットアップ術を極めよう!AppExert の開発者は、家族全員が一緒にいる場合でも、在宅勤務の技術を習得しています。祖父や曽祖父が共同家族で暮らしていた頃の記憶がよみがえりました。

2022 年、私たちのデジタル ライフはどこで終わり、「リアル ライフ」はどこから始まるのでしょうか?

20 年前のタイムトラベラーでさえ、日常生活におけるデジタルおよびインターネットベースのサービスの重要性に驚くことでしょう。MySpace、eBay、Napster などのプラットフォームは、高速化に焦点を合わせた世界がどのようなものになるかを示してくれました。

ニューロマーケティングの秘密科学

ニューロマーケティングの秘密科学

マーケティング担当者が人間の欲望を操作するために使用する、最先端の (気味が悪いと言う人もいます) メソッドを探ります。カートをいっぱいにして 3 桁の領収書を持って店を出る前に、ほんの数点の商品を買いに行ったことはありませんか? あなたは一人じゃない。

地理情報システムの日: GIS 開発者として学ぶべき最高の技術スタック

地理情報システムの日: GIS 開発者として学ぶべき最高の技術スタック

私たちが住んでいる世界を確実に理解するには、データが必要です。ただし、空間参照がない場合、このデータは地理的コンテキストがないと役に立たなくなる可能性があります。

Language