Sztywność matrycy i zastosowania matryc o niskiej sztywności

Około jedna matryca stopnia jest uważane za sztywne, jeśli się do jego pozycję do , trzeba zmiany co najmniej jego pozycji, dla niektórych . $n$ $\frac{n}{2}$ $n^{1+\epsilon}$ $\epsilon > 0$

Jeśli $n \times n$ macierzy $A$ jest sztywny, to najmniejszy program linii prostej obliczający $Ax$ ( $x$ jest wektorem wielkości $n$ ) ma albo rozmiar superliniowy, albo ma głębokość logarytmiczną.

Czy istnieje odwrotność do powyższego stwierdzenia?

Innymi słowy, czy istnieją zastosowania nietrywialnych i nieoczywistych matryc o niskiej sztywności pełnej rangi w TCS?

Czy istnieje pojęcie sztywności dla matryc o niższych szeregach (powiedz $\frac{n}{c}$ dla niektórych stałych $c$ )?

cc.complexity-theory

— T ....
źródło

+1, miło widzieć tutaj pytanie dotyczące sztywności, zaawansowany temat, ale nie jest to takie jasne. odwrotność wyrażenia byłaby czymś takim, jakby najmniejszy program linii prostej obliczający

A x

$A x$ był albo wielkością superliniową, albo superlogarytmiczną, to macierz

n \times n

$n \times n$ jest sztywna. dobrze? ale wydaje się to inne niż ostatnie pytanie o nietrywialne / nieoczywiste matryce o niskiej sztywności. wydaje się, że sztywność większości matryc, zarówno niskich, jak i wysokich, nie jest tak banalna ani oczywista ... istnieje wiele użytecznych matryc, które mają niską sztywność ... nie zbudowano żadnych nielosowych matryc o wysokiej sztywności!

— dniu

Jeśli macierz nie jest sztywna, możesz ją rozłożyć na gdzie jest macierzą niskiego rzędu, a jest macierzą rzadką. Programy liniowe zdefiniowane przez i można obliczać wydajnie (tj. Lepiej niż trywialnie), opierając się na właściwościach niskiej rangi i rzadkości. Oznacza to na przykład, że jeśli wymaga obwodu kwadratowego, to musi być sztywny (z odpowiednim doborem parametrów).

A

$A$

A = B + C

$A=B+C$

B

$B$

C

$C$

B

$B$

C

$C$

A

$A$

— Mahdi Cheraghchi,

może najpierw dobrze jest poprosić o przykłady matryc o nieoczywistej niskiej sztywności

— Sasho Nikolov

@vzn innym sposobem na stwierdzenie czegoś przeciwnego jest „czy matryce o niskiej sztywności mają małe liniowe obwody”. twoja odpowiedź jest dokładnie w odwrotnym kierunku (ani słowa o zastosowaniach tego rodzaju mniej sztywnych -> bardziej wydajnych), więc -1

— Sasho Nikolov

@MCH Dobra uwaga. Co może być lepszego niż trywialne? Robisz interesujący punkt, zmienię nieco pytanie.

— T ....

-3

bez dalszego wyjaśnienia pytania, oto próba / szkic odpowiedzi. sztywność macierzy ma głębokie powiązania z podstawowymi pytaniami w TCS / teorii złożoności, w tym dolnymi granicami obwodu, [1], a tym samym separacjami klas złożoności i teorią kodowania [2], a także innymi dziedzinami. [5] to fajna ankieta.

określenia „niski” i „wysoki” w odniesieniu do sztywności matryc są stosowane nieformalnie, a nie w ściśle określonym znaczeniu technicznym. [chociaż Friedman zdefiniował „silną” sztywność. [6]] losowe matryce są znane z wysokiej sztywności, ale w gruncie rzeczy jest to otwarty od 3,5 dziesięcioleci otwarty problem w tym obszarze, aby wyraźnie skonstruować dowolną matrycę o „znacznie wysokiej” sztywności.

pytanie nie definiuje dalej / nie wyjaśnia subiektywnych terminów „nietrywialny” lub „nieoczywisty” i zyska tam pewną swobodę.

w tym obszarze istnieje szereg badań dotyczących sztywności macierzy Hadamarda, które mają różne zastosowania / zastosowania w teorii kodowania i gdzie indziej.

wydaje się słuszne stwierdzenie, że możliwy do udowodnienia wysoki wynik sztywności przekroczyłby próg prowadzący przynajmniej do „nowych nietrywialnych następstw w teorii złożoności”, ale najbardziej znane granice macierzy Hadamarda nie wystarczają [3]. ale nie dowodzi to jednoznacznie, że mają ograniczoną „niską” sztywność. to w zasadzie ta sama historia z matrycami Vandermonde [także zastosowania w teorii kodowania] rozważane przez Lokama. [4]

tak więc podsumowując wszystko, co można powiedzieć, to że „słabe dolne granice sztywności” zostały udowodnione na niektórych matrycach, w tym na matrycach Hadamarda / Vandermonde'a.

wydaje się również, że w tym obszarze nie ma opublikowanych eksperymentów numerycznych, szacunków ani algorytmów.

[1] Boolean Function Complexity autorstwa Stasys Jukna, 2011, pkt 12.8 „sztywne matryce wymagają dużych obwodów”

[2] O sztywności matrycy i lokalnie samoregulujących kodach Zeev Dvir

[3] Ulepszone dolne granice na zagadnieniu macierzy Hadamarda Kashina / Razborova

[4] O sztywności Vandermonde Matrices Lokam

[5] Omówienie sztywności macierzy Mahdiego Cheraghchi

[6] J. Friedman. Uwaga na temat sztywności matrycy. Combinatorica, 13 (2); 235-239, 1993

— vzn
źródło