Abstract-Problemet att hitta den minsta-kvarts lösning till ett system av linjära ekvationer där den okända vektorn består av heltal, men matriskoefficienten och givna vektorn består av reella tal, uppstår i många tillämpningar: kommunikation, kryptografi, GPS, för att nämna några. Problemet är detsamma som att hitta närmaste lattice punkt till en given punkt och är känd för att vara NP-hård. I kommunikationstillämpningar är dock den givna vektorn inte godtycklig utan snarare en okänd latticepunkt som har störts av en additiv brusvektor vars statistiska egenskaper är kända. Därför, i detta dokument, snarare än att uppehålla sig vid det värsta-fall komplexitet heltal minsta-kvarts problem, vi studerar dess förväntade komplexitet, i genomsnitt över buller och över lattice. För algoritmen "sfäravkodning" av Fincke och Pohst finner vi ett slutet uttryck för den förväntade komplexiteten, både för det oändliga och finita lattice. Det visas i den andra delen av detta dokument att för ett brett spektrum av signal-till-buller-förhållanden (SNR) och antal antenner är den förväntade komplexiteten polynom, i själva verket ofta ungefär kubik. Eftersom många kommunikationssystem fungerar på bullernivåer för vilka den förväntade komplexiteten visar sig vara polynom, tyder detta på att maximal liknande avkodning, som hittills ansågs vara beräkningsbar, faktiskt kan genomföras i realtid-ett resultat med många praktiska konsekvenser.
Ekvation (12) kallas minst kvadrat problem och hitta exakt lösning är NP-hård REF.
On the sphere-decoding algorithm I. Expected complexity
{'venue': 'IEEE Transactions on Signal Processing', 'journal': 'IEEE Transactions on Signal Processing', 'mag_field_of_study': ['Computer Science', 'Mathematics']}