参数化切比雪夫插值的低阶张量逼近

（6） 图1通过tenso r网络图说明了这种所谓的TT分解【38】。如果TT等级保持适度，则通过存储而不是存储X TT co res来实现显著的内存减少：从O（nd）到O（dnr），其中r=max{r，…，rd}和n=max{n，…，nd}。对于低TT秩的张量，一些操作可以在TT格式中非常便宜地进行。让我们首先考虑两个张量X，Y的内积∈ Rn×···××nDdefined ashX，Yi=hvec（X），vec（Y）i=nXi=1···ndXid=1X（i，…，id）Y（i，…，id），（7），其中vec（·）将张量的条目堆叠成一个长向量。当X和Y都处于TT分解时，相应的tensornetwork图如图2所示。可以看出，（7）中的总和变成了X和Y的TT核之间的收缩。B通过从左到右进行这些核收缩，内积的评估成本从O（nd）降低到O（dnr），其中r表示所有相关TT秩的最大值。图2：TT分解中两个d=5阶张量的内积。张量X之间的模u矩阵乘法∈ Rn×·······························∈ Rm×nu产生张量Z∈ Rn×···nu-1×m×nu+1·································-1，j，iu+1···，id）=nuXiu=1X（i，···，id）M（j，ik），j=1，m、 我们将用Z=X×kM表示此操作。如果X在TT分解（6）中，则通过执行Uu与M的模式2矩阵乘法，可以直接获得Z的TT分解。要让cMdenote避免将mw与向量相乘的成本，这需要O（cMnr）操作，而不是O（cMnd-1） 当X是一般张量时，需要进行运算。2.3完成算法完成算法的目标是从一小部分条目中构造给定的数据集。

由于这显然是一项不适定任务，因此需要添加一些正则化，例如平滑条件。在这项工作中，我们使用[45]中提出的完备算法，在包含价格和结构P的张量P上施加低TT秩。在下文中，我们简要总结了[45]的方法。让A∈ Rn×·······································Ohm  已知{1，n}×···×{1，nd}。当目标是为该数据设置固定（低）TT秩r=（r，…，rd）的张量时，补全采用约束优化问题minx | | P的形式Ohm十、- POhmA | |以X为准∈ Mr：={X∈ Rn×··××nd | rankTT=r}，（8）其中POhmX表示上的正交投影Ohm k·k是内积（7）诱导的范数。众所周知，mr是一个光滑的嵌入子流形，它使我们能够将黎曼优化技术应用于（8）。具体而言，在【45】中，建议采用黎曼共轭梯度（CG）方法（见【45】中的算法1）。该方法生成停留在流形上的迭代，然后可以以TT格式高效地存储和操作。一次迭代需要O（dnr+d|Ohm|r） 操作，其中|Ohm| 表示的基数Ohm.我们的黎曼CG停止标准旨在通过数据和所选TT等级达到一定的精确度。根据[45]，我们选择一个测试集Ohm例如，100个额外的参数样本不在训练集中Ohm.

让XKD进行黎曼CG算法的第k次迭代，我们测量了训练和测试集上的误差：Ohm（Xk）：=kPOhmA.- POhmXkkkPOhmAk，OhmC（Xk）：=kPOhm加利福尼亚州- POhmCXkkkPOhm结块。一旦这些错误停滞不前，即|停止算法Ohm（Xk）- Ohm（Xk+1）| |Ohm（Xk）|<δ和|OhmC（Xk）- OhmC（Xk+1）| |OhmC（Xk）|<δ，（9）对于一些小δ>0.2.3.1的自适应秩和自适应采样策略，为了建立优化问题（8），还有两个问题有待讨论：TT秩r的选择和合适的训练集Ohm. 对于我们的应用程序，这些是未知的，因此需要自适应选择。关于TT等级的选择，我们遵循din[45]提出的自适应策略。我们首先求解（8），求出TT秩的最小合理选择，r=（1，…，1）。这种选择很可能无法获得令人满意的准确度，测试集的误差相对较大。为了降低它，将o bta定义的解用作黎曼CG的起始值，再次应用于（8），但这一次TT秩增加r=（1，2，1，…，1），如【45】所述。参见【47】，了解矩阵完成上下文中的greedyrank更新程序。通过循环增加每个TT秩ru来重复所述过程。整个算法停止运行，因为增加任何TT r ANK都不会改善测试集错误或达到最大可能秩rmaxis；参见算法1。算法1自适应排名策略输入：采样/测试t集数据Ohm, OhmC、 最大秩rmax，验收参数ρ≥ 0输出：使用自适应选择的TT秩r，ru完成张量X≤ rmax。1： 具有TT秩r=（1，…，1）2:X的X随机张量← 使用起始猜测X3得出的黎曼CG结果：锁定=04：u=15：锁定时<d- 最大νrν<rmaxdo6:Xnew（&M）← 增加X至（r，…，ru）的第u个等级-1，ru+1，ru+1。

，rd）7:X新← 使用起始猜测Xnew8的黎曼CG结果：if（OhmC（Xnew）- OhmC（X））>-ρthen9：锁定← 锁定+1%还原步骤10：else11：锁定← 0，X← X新%ac c ept步骤12：结束if13：u← 1+（umo d d- 1） 14：结束采样集的自适应选择Ohm, 我们提出了两种不同的策略。其核心思想是逐步扩大Ohm 为了提高张量的近似性。这两种策略也与算法1相结合，它们仅在误差测量方面有所不同。第一种适应性抽样策略的步骤如下所示。1、从样本集开始Ohm 小尺寸和测试集OhmCof特定处方尺寸|OhmC |。运行算法1.2。测量测试集上的相对误差Ohm如果满足停止标准，则可以停止。如果不满足，则添加测试集OhmCto样本集Ohm 并创建一个新的大小测试集|OhmC |。在我们的应用中，这与使用参考方法计算切比雪夫网格上的新期权价格相关。3、使用前一步结果的秩r=（1，…，1）近似值作为CG算法的初始猜测，从第2行再次运行算法1直到最后。4、重复1-3，直到达到最大采样百分比或满足先验chosenstopping标准。算法2中的伪代码总结了第一种策略。第二，我们提出的自适应采样策略也是以类似的方式设计的。

唯一的区别是，误差是在先验定义的集合算法2自适应采样策略1输入：初始采样数据P上测量的OhmA、 最大秩rmaxfor秩自适应，最大允许大小百分比p（共个Ohm)输出：TT秩r，ru的完成张量X≤ rmax1：创建测试集OhmCnewsuch那Ohm ∩ OhmCnew=2： 使用运行算法1Ohm, OhmCnew并完成张量Xc。3： errnew（新建）← OhmCnew（Xc）4:5:while|Ohm|/尺寸（A）<p do6：errold← 错误7：￠X← Xc8的秩（1，…，1）近似值：Ohm寒冷的← OhmCnew9：创建新的测试集OhmCnewsuch那OhmCnew公司∩ Ohm冷=10: Ohm ← Ohm ∪OhmCold11：使用Ohm, OhmCNE和▄X作为起始猜测。从中得到完整的张量xC。12： errnew（新建）← OhmCnew（Xc）13：如果满足停止标准，则14：中断15：结束if16：结束while17:18：X← XcΓ且未打开OhmC、 每一步都会发生变化。因此，该策略遵循与第一个策略相同的步骤，唯一不同的是，在步骤2中，我们测量了集合Γ上的误差，这是之前定义的。通过替换算法2WITHERNEW中的第3行和第12行，可以获得总结此Second策略的算法← Γ（Xc）。13号线的停车标准也可以用不同的方式定义。如果满足以下条件之一，我们选择停止算法：1。如果errnew<tol，其中tol为规定公差；2、如果| errnew- errold |<tol′，其中tol′是规定的公差；3.

如果u，使得ru（Xc）=rmax。第一个标准允许我们在错误或低于某一水平时立即停止，第二个标准允许我们在错误停滞时停止算法，最后一个标准允许我们在TT秩至少在一种模式u中达到最大允许秩时停止算法。在下一节中，我们将在已知解的问题上测试新的自适应s采样策略。2.3.2自适应抽样策略的数值测试我们考虑了[45]中第5.4.2章的问题，并将我们的自适应抽样策略应用于此，以比较它们，并调查它们的优缺点。我们预计这两种策略在精确度和压缩方面的性能相似。在这个数值例子中，以及在本文的其余部分中，我们选择k·k为2-范数，δ=10-4英寸（9）。问题包括离散化函数F：[0，1]→ R、 f（x）=exp(-kxk）在每种模式下，在[0，1]上使用n=20个等距离散点。我们的目标是在网格中构造包含函数值的张量。在算法2中，我们将最大秩设为rmax=（1，7，7，7，1），然后从初始采样集开始Ohm 令人满意|Ohm|/n=0.01。此外，我们将算法1的接受参数ρ设置为ρ=10-4、为了分析错误的行为，我们不采用任何停止标准，而是让我们的自适应采样策略运行到|Ohm|/尺寸（A）>0.25。每个的大小Ohm对于第二个策略，Cis设置为2000且|=3000。

图3和图4显示了两种不同策略的结果。0 0.05 0.1 0.15 0.2 0.25Size-4-3-2-1相关误差onCrank：1 5 4 4 4 1 1 1 1 1 4 4 4 1 1 1 1 1 1 4 4 4 1 1 1 1 1 1 4 4 1 1 1 1 4 4 1 1 1 1 1 1 1 4 4 1 1 1 1 1 3 3 1 1 1 1 3 3 1 1 1 1 1 1 1 4 4 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 4 4 4 4 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 4 4 4 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 4 4 4 4 4 4 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1银行：1 4 4：1 4 4 41数据库：1 4 4 4数据库：1 4 4 4图3：变量测试集的相对误差OhmC对于不同的采样集大小，不适用的采样策略1.0 0 0.05 0.1 0.15 0.2 0.25Size-4-3-2-1秩相关误差：1 5 4 1秩：1 5 4 4 1秩：1 5 4 4 1秩：1 3 3 1秩：1 5 4 4 1秩：1 3 3 3 1秩：1 4 4 4 4 1秩：1 4 4 4 44数据库：1 4 4数据库：1 4 4数据库：1 4数据库：1 4数据库：1 4图4：自适应采样策略中不同采样集大小的相对误差2。首先，我们观察到两种策略最终都达到了相同的精度和相同的最终TT等级，这使得它们都是有效的。我们观察到图3中的振荡行为。这种非平滑衰减是可以预期的，因为在每个步骤中，误差都是在不同的测试集上测量的OhmC、 我们观察到，当|Ohm| 增加。这表明整个张量存在误差停滞，不能通过扩大张量来改善OhmC进一步。另一方面，第二种策略中的错误几乎是单调的，并且比前一种情况中的错误出现得更早。这是因为我们在固定集Γ上测量It。

实际上，Second策略的早期错误停滞是可以参考的，因为它触发了停止标准2。然而，第二种策略的缺点是，评估集合Γ中张量的初始额外成本。在第3节的数值实验中，我们选择了第一种策略y，因为停止标准1是触发红色，所以它更有利。2.4组合方法我们现在可以将概念和算法结合起来，以开发高维张量切比雪夫插值的有效程序。我们希望根据向量p=（p，····，pd）对期权进行定价。可以合理地假设，参数sp的每个组合都属于一个紧超矩形[p，p]×[p，p]×····×[pd，pd]。例如，如果到期时间T等于一组变化的参数，我们可以假设∈ [0.05, 2]; 与其他Payoff或模型参数类似。正如文献[14]中所介绍的那样，组合方法包括两个阶段：在线阶段和在线阶段。2.4.1 O形相位-p的计算O形相位开始于以下操作：1。修正插值o ordern=（n，…，nd），并根据先验选择的s ubs e t计算传感器P的条目（如（4）所定义Ohm 使用参考定价技术。2、采用张量补全和自适应采样策略（算法2），以获得TT格式的张量P的低阶近似值。为简单起见，我们再次用P表示获得的P的低阶近似值。在oêine阶段的最后一步，我们构造了插值系数definedin（4）。我们用C表示系数的张量o∈ R（n+1）×（n+1）×···×（nd+1）。

因此，其条目由（根据第2.1节和第2.2节调整顺序）C（i，i，···，id）=ci给出-1，我-1，···，id-1、（10）对于ij=1、····、nj+1和j=1、···、d，可以有效地计算出张量C的inTT格式，如以下小节所述。2.4.2 CIn相位系数计算为了解释算法，我们首先考虑简单情况d=1。在这种情况下，p和C是R（n+1）×1，其中nis是所选的插值顺序。c的条目由c（j+1）=n>j>0nnX′k=0P（k+1）cos给出jπkn, j=0，···，n，因此整个向量C n可以通过矩阵向量乘法C=n计算. . .cos（πn）。cos（π（n-1） n）cos（π）。。。。。。。。。。。。。。。cos（π（n-1） n）。cos（π（n-1） n）cos（π（n- 1） ）cos（π）。cos（π（n- 1） ）cos（πn）P、 （11）我们用Fn表示∈ R（n+1）×（n+1）矩阵乘以（11）中的P。对于一般维度d>1，可以通过第2.2节中定义的模式u乘法，通过将P与FNI（i=1，····，d）按次顺序相乘来计算相同的结果和张量协插值系数。算法3给出了有效计算C的最终过程。算法3有效计算TT格式的CInput：张量P，包含切比雪夫网格中的期权价格输出：如（10）所定义的张量C，TT格式1：计算（11）中的FNA。2： C类← P×Fn3：对于m=2，d do4：计算Fnm5：C← C×mFnm。6： 请注意，如果n=···=nd=：n（例如，在我们的数值实验第3节中），则可以通过计算矩阵fnonlonce来进一步简化算法3。矩阵Fniallows的特殊结构使我们能够应用基于傅里叶变换的快速算法，该算法以O（rn log（n））（而不是第3节中提到的O（rn））计算每个模式的乘法。

因此，计算C的总复杂性为O（dnrlog（n））。通过执行步骤3，最终可以完成o形阶段。如算法3.2.4.3在线阶段中所述，构造张量C。我们以TT格式存储了C后，就可以在在线阶段通过插值来计算每个期权价格。对于参数p的任何特定选择，我们首先执行步骤4。计算p中的切比雪夫张量bas为（3）。此步骤返回张量Tp∈ 我们以TT格式存储的TT秩（1，···，1）的R（n+1）×（n+1）×（n+1）×······（nd+1）。（2）中定义的插值价格现在可以重新定义为内部产品in（价格（·））（p）=hC，Tpi。（12） 我们组合方法的最后一步定义为5。按TT格式计算内插价格（12），如（7）所示。如果我们考虑每个维度中的固定插值阶数n，如果P和C的TT ranksof近似为r，则执行步骤3和步骤5的总成本由O（dnr+dnrlog（n））给出。这两个步骤通过图5中的张量网络图（对于d=5）表示，其中我们用p的pithecore张量和Tp的Tithe张量表示。PPPPP FNFNFNFNFNTTTT▄n▄nr▄n▄nr▄n▄nr▄n▄nr▄n▄n▄n▄图5：以TT格式表示整个插值过程asin（2）和（4）的张量网络图，其中d=5。