I detta dokument 1, Vi studerar matris skalning och balansering, som är grundläggande problem i vetenskaplig databehandling, med en lång rad arbete på dem som går tillbaka till 1960-talet. Vi tillhandahåller algoritmer för båda dessa problem som, ignorera logaritmiska faktorer som omfattar dimensionen av inmatningsmatrisen och storleken på dess poster, båda kör i tid O m log ε log 2 (1/ε) där ε är den mängd fel vi är villiga att tolerera. Här representerar δ förhållandet mellan de största och de minsta posterna i de optimala skalningarna. Detta innebär att våra algoritmer körs i nästan linjär tid när δ är kvasi-polynom, vilket i synnerhet omfattar fallet med strikt positiva matriser. Vi kompletterar våra resultat genom att tillhandahålla en separat algoritm som använder en inre punktmetod och körs i tid O(m 3/2 log(1/ε)). För att fastställa dessa resultat utvecklar vi ett nytt ramverk för andra ordningens optimering som gör det möjligt för oss att behandla båda problemen på ett enhetligt och principfast sätt. Detta ramverk identifierar en viss generalisering av linjär systemlösning som vi effektivt kan använda för att minimera en bred klass av funktioner, som vi kallar andra ordningen robust. Vi visar sedan att i samband med de specifika funktioner fånga matrisskalning och balansering, kan vi utnyttja och generalisera arbetet med Laplacian systemlösning för att göra algoritmer som erhållits via detta ramverk mycket effektivt.
I synnerhet innebär detta att algoritmen i REF är nära linjär tid i en pseudorandom instans enligt definitionen i definition 4.3.2 (inte nödvändigtvis strikt positiv).
Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods
{'venue': '2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)', 'journal': '2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)', 'mag_field_of_study': ['Computer Science', 'Mathematics']}