為什麼正交基使得在格中求解 SVP 變得更容易？
我一直在瀏覽https://courses.maths.ox.ac.uk/node/view_material/12662並提到：
一些基礎使 SVP 更容易：
- “好”基具有更短的向量範數
- “好”基具有幾乎正交的向量
我認為較短向量範數有用的原因是，如果我們使用諸如 LLL 之類的算法，我們將有一個更好的起點，並且減少的會更少？但是，我不確定為什麼幾乎正交的基向量會使 SVP 更容易。僅僅是因為它以某種方式使 LLL(-BKZ) 等算法更容易減少基向量嗎？
僅僅是因為它以某種方式使 LLL(-BKZ) 等算法更容易減少基向量嗎？
這有點倒退——基礎減少的目的是找到一個“更短”和“更正交”的基礎，然後將其用於有用的應用程序。
Babai 的最近平面是一種相當著名的算法，用於求解 CVP 的近似形式，它是相對於某個固定基定義的 $ B = [b_1,\dots,b_n] $ 的格子。如果 $ x\in\mathbb{R}^n $ ， 和：
- $ v $ 是 Babai 的最近平面的輸出，並且
- $ v_{opt} $ 是最接近的向量 $ x $ ,
那麼可以證明： $$ \lVert v-v_{opt}\rVert_2^2 \leq \frac{1}{4}\sum_{i = 1}^n \lVert b_i^\rVert_2^2 $$ 在哪裡 $ {b_1^,\dots, b_n^*} $ 是 Gram-Schmidt 正交化 $ B $ . 請注意，由於 Gram-Schmidt 正交化僅適用於基本操作，因此具有：
$$ \det([b_1^,\dots, b_n^]) = \det B $$
例如總產品 $ \prod_{i=1}^n \lVert b_i^\rVert_2 = \det B $ 保持不變。應該很容易看出，如果這個“ $ \det B $ 質量”是“均勻分佈”在所有 $ {b_1^,\dots, b_n^} $ ，例如，如果基礎很短且幾乎正交*。