Vi studerar problemet med att få fram effektiva, deterministiska, svart-box polynomiska identitetstestningsalgoritmer för djup-3 set-multilinjära kretsar (över godtyckliga fält). Denna klass av kretsar har en effektiv, deterministisk, vit-box polynom identitetstestande algoritm (på grund av Raz och Shpilka [36], men har ingen känd sådan Black-box algoritm. Vi omarbetar detta problem som en fråga om att hitta en lågdimensionell subrymd H, spännt av rank 1 tensors, så att alla icke-noll tensor i den dubbla rymdkern (H) har hög rang. Vi får explicita konstruktioner av i huvudsak optimal storlek slaguppsättningar för tensorer av grad 2 (matriser), och få den första kvasipolynom storlek slaguppsättningar för godtyckliga tensorer. Vi visar också kopplingar till uppgiften att utföra lågvärdig återhämtning av matriser, som studeras inom området komprimerad avkänning. Lågvärdig återhämtning ber (säg, över R) att återställa en matris M från få mätningar, under löftet att M är rank ≤ r. I detta arbete, begränsar vi vår uppmärksamhet till att återvinna matriser som är exakt rang ≤ r med hjälp av deterministiska, icke-adaptiva, linjära mätningar, som är fria från buller. Över R ger vi en uppsättning (av storlek 4nr) av sådana mätningar, från vilka M kan återvinnas i fält O(rn 2 + r 3 n), och antalet mätningar är i huvudsak optimalt. Dessutom kan mätningarna tas för att vara alla rang-1 matriser, eller alla glesa matriser. Såvitt vi vet var inga explicita konstruktioner med dessa egenskaper kända innan detta arbete. Vi ger också en mer formell koppling mellan lågrankade 9 * En fullständig version av detta dokument finns på http://arxiv. org/abs/1111.0663 † recovery och uppgiften sparse (vektor) recovery: varje sparsecovery-algoritm som exakt återvinner vektorer av längd n och sparity 2r, med hjälp av m icke-adaptiva mätningar, ger ett lågvärdigt recovery system för exakt recovery n × n matriser av rang ≤ r, vilket gör 2nm icke-adaptiva mätningar. Dessutom, om sparse-återvinning algoritmen körs i tid τ, då låg-rank återställningsalgoritm körs i tid O (rn 2 +nτ ). Vi får denna reduktion med linjär-algebraiska tekniker, och inte med konvex optimering, som är vanligare i komprimerade avkänningsalgoritmer. Slutligen gör vi också en koppling till rank-metriska koder, som studeras i kodningsteori. Dessa är koder med kodord som består av matriser (eller tensorer) där avståndet av matriser M och N är rang(M − N ), i motsats till den vanliga hamming metrisk. Vi får i stort sett optimala koder över matriser, och ger en effektiv avkodningsalgoritm. Vi får koder över tensorer också, med sämre hastighet, men ändå med effektiv avkodning.
Å andra sidan, om vi begränsar oss till set-multilinjära djup-3 kretsar då den träffande uppsättningen av REF är polynomiellt mindre än den uppsättning som vi konstruerar här.
On identity testing of tensors, low-rank recovery and compressed sensing
{'venue': "STOC '12", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}