înregistrare Logare
Puncte:0
cryptobeginner avatar Crypto

NTL: Rezolvați cea mai apropiată problemă vectorială pentru matricea non-pătrată folosind LLL/Algoritmul cel mai apropiat plan

drapel cn
cryptobeginner

Să presupunem că am o matrice $A \in \mathbb{Z}^{m \times n}$, $m > n$, care formează o bază a unei rețele. Dat un vector țintă vector $t = Ax + e$, $t,e \in \mathbb{Z}^m$,$x \in \mathbb{Z}^n$, vreau să găsesc cel mai apropiat vector (aproximativ) din rețea $\mathcal{L}(A)$ la $t$.

Am vrut să folosesc cel mai apropiat algoritm al lui Babai, în special implementarea NTL NTL::NearVector pentru a rezolva această problemă (aproximativ) folosind LLL. Cu toate acestea, mi se pare că în literatură și cu siguranță în pachetul de software, algoritmul planului cel mai apropiat al lui Babai necesită o rețea de rang complet?

Ce alte tehnici/înglobări pot folosi pentru a rezolva cea mai apropiată problemă vectorială pe o rețea cu dimensiune mai mare decât rangul? Aș putea extinde matricea cu coloane cu vector zero?

89
0 + 0
lwe
Mark avatar
drapel ng
Mark
În norma $\ell_2$, ar trebui să fie suficient să proiectați vectorul pe intervalul (real) al rețelei (care este un subspațiu de rang $n$), apoi rotiți ortogonal acest subspațiu pentru a fi izomorf la $\mathbb{R} ^n\ori\{0\}^{m-n}$. Totuși, nu știu cum să fac asta în NTL, așa că voi lăsa doar comentariul.
0
Răspunde
Puncte:1
Don Freecs avatar Crypto
drapel sz
Don Freecs

nu Algoritmul planului cel mai apropiat al lui Babai nu are nevoie de o rețea de rang complet uită-te la această hârtie Aici.

0 + 0
drapel romania
SEF 777
întrebarea această in alte limbi:

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.