Abstrakt. Följande problem beaktas: med en matris A i Rm', (m rader och n kolumner), en vektor b i Rm, och 6 > 0, beräkna en vektor x som uppfyller IIax bl[2 <_ 6 om sådana finns, så att x har det minsta antalet icke-noll poster över alla sådana vektorer. Det visas att problemet är NP-hård, men att den välkända giriga heuristic är bra genom att den beräknar en lösning med högst [18 Opt(6/Z)lla + I1 ln(llbl12/6)] icke-noll poster, där Opt(6/2) är det optimala antalet icke-noll poster vid fel 6/2, A är den matris som erhålls genom att normalisera varje kolumn av A med avseende på L2 norm, och A + är dess pseudo-invers. Nyckelord, glesa lösningar, linjära system AMS ämnesklassificering. 1 till 68Q25. Inledning. Problemet med att beräkna en gles ungefärlig lösning till ett linjärt system är ett grundläggande problem vid matrisberäkning. För matriser över reals, problemet (variant därav) har studerats under namnet "subset selection" i statistisk modellering av Golub och Van Loan (1983). För binära matriser har problemet studerats som "minimiviktlösning" vid felkorrigerande kodning av Gallager (1968). Det relaterade "sparse null-space" problemet är av intresse för icke-linjär optimering; se Coleman och Pothen (1986). Dessutom kan "minimum set cover" problem ses som datorisering en gles lösning till Ax >_ b, där alla poster är binära och ojämlikheten är entry-wise; se Garey och Johnson (1979), Johnson (1974). Vår specifika motivation för att studera problemet är följande. En allmänt använd teknik för interpolering av oregelbundet fördelade prover i högre dimensioner är tekniken för radiell interpolering; se Hardy (1988). Kort sagt, tilldela var och en av de angivna provtagningspunkterna en koefficient. Interpolantens värde vid en ny punkt är den viktade summan av dessa koefficienter, där vikterna är avståndet mellan respektive prov från den nya punkten. Koefficienter själva är lösningen på det linjära ekvationssystemet som erhålls genom att utvärdera interpolanten vid var och en av de givna punkterna och likställa dem med respektive provvärden; Michelli (1986) har visat att det linjära systemet alltid är nonsingulärt. För att lösa det ovannämnda linjära systemet är två frågor av intresse. (1) Kostnaden för utvärdering av interpolanten vid en allmän punkt ökar med antalet icke-nollkoefficienter i lösningen. Därför är det önskvärt att ha så få icke-nollvärden som möjligt, samtidigt som man tolererar något fel i
Våra resultat är beroende av en generalisering av det glesa approximationsproblem som formellt föreslogs av Natarajan REF : givet A  på R m×n, en vektor b - R m, och > 0, hitta en vektor x - R n uppfyller Ax - b 2 ≤ sådan att x har de minsta icke-noll poster över alla sådana vektorer.
Sparse Approximate Solutions to Linear Systems
{'venue': 'SIAM J. Comput.', 'journal': 'SIAM J. Comput.', 'mag_field_of_study': ['Computer Science', 'Mathematics']}