För varje fast konstant α > 0, utformar vi en algoritm för beräkning av k-sparse Walsh-Hadamard transform (dvs. Diskrete Fourier Transform över Booleska kuben) av en N-dimensionell vektor x  och R N i tiden k 1+α (log N) O(1). Specifikt, algoritmen ges frågeåtkomst till x och beräknar en k-sparsex  på R N som uppfyller x −x 1 ≤ c x − H k (x) 1 för en absolut konstant c > 0, varx är omvandlingen av x och H k (x) är dess bästa k-sparse approximation. Vår algoritm är helt deterministisk och använder bara icke-adaptiva frågor till x (dvs. alla frågor bestäms och utförs parallellt när algoritmen startar). Ett viktigt tekniskt verktyg som vi använder är en konstruktion av nästan optimala och linjära förlustfria kondensorer, vilket är en noggrann omedelbarion av GUV kondenser (Guruswami et al. [2009]............................................................................................................... Dessutom utformar vi ett deterministiskt och icke adaptivt 1 / 1 komprimerat avkänningssystem baserat på allmänna förlustfria kondensorer som är utrustade med en snabb rekonstruktionsalgoritm som körs i tid k 1 + α (log N) O(1) (för GUV-baserad kondensor) och är av oberoende intresse. Vårt system förenklar och förbättrar avsevärt en tidigare expansionsbaserad konstruktion tack vare Berinde, Gilbert, Indyk, Karloff och Strauss [Berinde et al. Under 2008]........................................................................................... Våra metoder använder linjära förlustfria kondensorer i en svart låda mode; därför skulle eventuella framtida förbättringar av explicita konstruktioner av sådana kondensorer omedelbart översätta till förbättrade parametrar i vårt ramverk (potentiellt leder till k(log N) O(1) rekonstruktionstid med en reducerad exponent i polylogaritmisk faktor, och eliminera den extra parametern α). Genom att låta algoritmen använda slumpmässighet medan den fortfarande använder icke-adaptiva frågor kan algoritmens körtid förbättras till Õ(k log 3 N). Mahdi Cheraghchi och Piotr Indyk. Detta beslut träder i kraft den tjugonde dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning. Nästan optimal deterministisk algoritm för sparse Walsh-Hadamard transform.
Nyligen utvecklar REF en deterministisk algoritm för beräkning av en gles WHT i tiden O(K 1+ log O(1) N ) med en godtycklig konstant > 0.
Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}