I denna uppsats, motiverad av nätverksinferens och tomografi applikationer, studerar vi problemet med kompressiv avkänning för glesa signalvektorer över grafer. I synnerhet är vi intresserade av att återvinna glesa vektorer som representerar egenskaperna hos kanterna från en graf. Till skillnad från befintliga kompressiva avkänningsresultat måste de kollektiva additiva mätningarna vi tillåts göra följa uppkopplade vägar över den underliggande grafen. För en tillräckligt ansluten graf med n noder, det visas att, med hjälp av O(k log(n)) vägmätningar, vi kan återställa någon k-sparse länk vektor (med inte mer än k nonzero element), även om mätningarna måste följa grafen sökvägen begränsningar. Vi visar främst att beräkningseffektiv 1 minimering kan ge teoretiska garantier för att sådana k-sparse vektorer kan härledas med O(k log(n)) vägmätningar från grafen. Detta dokument presenterades som en del av det viktigaste tekniska programmet på IEEE INFOCOM 2011 978-1-4244-9921-2/11/$26.00 ©2011 IEEE
Xu och al. REF visar att en länk-metrisk vektor med högst k icke-noll-element kan återvinnas från O(k · log(n)) (där n är antalet nätverksnoder) vägmätningar med hjälp av kompressiv avkänning.
Compressive sensing over graphs
{'venue': '2011 Proceedings IEEE INFOCOM', 'journal': '2011 Proceedings IEEE INFOCOM', 'mag_field_of_study': ['Mathematics', 'Computer Science']}