Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Foundations of Computational Mathematics
Erschienen in: Foundations of Computational Mathematics 2/2012

01.04.2012

Learning Functions of Few Arbitrary Linear Parameters in High Dimensions

verfasst von: Massimo Fornasier, Karin Schnass, Jan Vybiral

Erschienen in: Foundations of Computational Mathematics | Ausgabe 2/2012

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Let us assume that f is a continuous function defined on the unit ball of ℝ d , of the form f(x)=g(Ax), where A is a k×d matrix and g is a function of k variables for k≪d. We are given a budget m∈ℕ of possible point evaluations f(x i ), i=1,…,m, of f, which we are allowed to query in order to construct a uniform approximating function. Under certain smoothness and variation assumptions on the function g, and an arbitrary choice of the matrix A, we present in this paper
1.
a sampling choice of the points {x i } drawn at random for each function approximation;
 
2.
algorithms (Algorithm 1 and Algorithm 2) for computing the approximating function, whose complexity is at most polynomial in the dimension d and in the number m of points.
 
Due to the arbitrariness of A, the sampling points will be chosen according to suitable random distributions, and our results hold with overwhelming probability. Our approach uses tools taken from the compressed sensing framework, recent Chernoff bounds for sums of positive semidefinite matrices, and classical stability bounds for invariant subspaces of singular value decompositions.
Vorheriger Artikel Superinterpolation in Highly Oscillatory Quadrature

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Literatur
1.
R. Ahlswede, A. Winter, Strong converse for identification via quantum channels, IEEE Trans. Inf. Theory 48(3), 569–579 (2002). MathSciNetMATHCrossRef
2.
E. Arias-Castro, Y.C. Eldar, Noise folding in compressed sensing, IEEE Signal Process. Lett. 18(8), 478–481 (2011). CrossRef
3.
R.G. Baraniuk, M. Davenport, R.A. DeVore, M. Wakin, A simple proof of the restricted isometry property for random matrices, Constr. Approx. 28(3), 253–263 (2008). MathSciNetMATHCrossRef
4.
H. Bauschke, H. Borwein, On projection algorithms for solving convex feasibility problems, SIAM Rev. 38(3), 367–426 (1996). MathSciNetMATHCrossRef
5.
6.
E.J. Candès, Ridgelets: estimating with ridge functions, Ann. Stat. 31(5), 1561–1599 (2003). MATHCrossRef
7.
E.J. Candès, D.L. Donoho, Ridgelets: a key to higher-dimensional intermittency? Philos. Trans. R. Soc., Math. Phys. Eng. Sci. 357(1760), 2495–2509 (1999). MATHCrossRef
8.
E.J. Candès, J. Romberg, T. Tao, Stable signal recovery from incomplete and inaccurate measurements, Commun. Pure Appl. Math. 59(8), 1207–1223 (2006). MATHCrossRef
9.
E.J. Candès, T. Tao, The Dantzig selector: statistical estimation when p is much larger than n, Ann. Stat. 35(6), 2313–2351 (2007). MATHCrossRef
10.
A. Cohen, W. Dahmen, R.A. DeVore, Compressed sensing and best k-term approximation, J. Am. Math. Soc. 22(1), 211–231 (2009). MathSciNetMATHCrossRef
11.
A. Cohen, I. Daubechies, R.A. DeVore, G. Kerkyacharian, D. Picard, Capturing ridge functions in high dimensions from point queries, Constr. Approx. 35(2), 225–243 (2012). CrossRef
12.
R. Courant, D. Hilbert, Methods of Mathematical Physics, II (Interscience, New York, 1962).
13.
R.A. DeVore, G. Petrova, P. Wojtaszczyk, Instance optimality in probability with an ℓ 1-minimization decoder, Appl. Comput. Harmon. Anal. 27(3), 275–288 (2009). MathSciNetMATHCrossRef
14.
15.
M. Fazel, Matrix rank minimization with applications, Ph.D. thesis, Stanford University, Palo Alto, CA, 2002.
16.
M. Fornasier, Numerical methods for sparse recovery, in Theoretical Foundations and Numerical Methods for Sparse Recovery, ed. by M. Fornasier, Radon Series on Computational and Applied Mathematics (De Gruyter, Berlin, 2010). CrossRef
17.
M. Fornasier, H. Rauhut, Compressive sensing, in Handbook of Mathematical Methods in Imaging, vol. 1, ed. by O. Scherzer (Springer, Berlin, 2010), pp. 187–229.
18.
S. Foucart, A note on ensuring sparse recovery via ℓ 1-minimization, Appl. Comput. Harmon. Anal. 29(1), 97–103 (2010). MathSciNetMATHCrossRef
19.
G. Golub, C.F. van Loan, Matrix Computations, 3rd edn. (Johns Hopkins University Press, Baltimore, 1996). MATH
20.
F. John, Plane Waves and Spherical Means Applied to Partial Differential Equations (Interscience, New York, 1955). MATH
21.
M. Ledoux, The Concentration of Measure Phenomenon (American Mathematical Society, Providence, 2001). MATH
22.
23.
E. Novak, H. Woźniakowski, Tractability of Multivariate Problems, Volume I: Linear Information, EMS Tracts in Mathematics, vol. 6 (Eur. Math. Soc., Zürich, 2008). MATHCrossRef
24.
E. Novak, H. Woźniakowski, Approximation of infinitely differentiable multivariate functions is intractable, J. Complex. 25, 398–404 (2009). MATHCrossRef
25.
R.I. Oliveira, Sums of random Hermitian matrices and an inequality by Rudelson, Electron. Commun. Probab. 15, 203–212 (2010). MathSciNetMATHCrossRef
26.
S. Oymak, K. Mohan, M. Fazel, B. Hassibi, A simplified approach to recovery conditions for low-rank matrices, in Proc. Intl. Symp. Information Theory (ISIT) (2011).
27.
28.
B. Recht, M. Fazel, P. Parillo, Guaranteed minimum rank solutions to linear matrix equations via nuclear norm minimization, SIAM Rev. 52(3), 471–501 (2010). MathSciNetMATHCrossRef
29.
M. Rudelson, R. Vershynin, Sampling from large matrices: an approach through geometric functional analysis, J. ACM 54(4), 21 (2007) 19 pp. MathSciNetCrossRef
30.
W. Rudin, Function Theory in the Unit Ball of ℂ n (Springer, New York, 1980). CrossRef
31.
K. Schnass, J. Vybíral, Compressed learning of high-dimensional sparse functions, in Proc. ICASSP11 (2011).
32.
G.W. Stewart, Perturbation theory for the singular value decomposition, in SVD and Signal Processing, II, ed. by R.J. Vacarro (Amsterdam, Elsevier, 1991).
33.
34.
35.
H. Weyl, Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller Differentialgleichungen (mit einer Anwendung auf die Theorie der Hohlraumstrahlung), Math. Ann. 71, 441–479 (1912). MathSciNetMATHCrossRef
36.
P. Wojtaszczyk, ℓ 1 minimisation with noisy data, Preprint (2011).
Metadaten
Titel
Learning Functions of Few Arbitrary Linear Parameters in High Dimensions
verfasst von
Massimo Fornasier
Karin Schnass
Jan Vybiral
Publikationsdatum
01.04.2012
Verlag
Springer-Verlag
Erschienen in
Foundations of Computational Mathematics / Ausgabe 2/2012
Print ISSN: 1615-3375
Elektronische ISSN: 1615-3383
DOI
https://doi.org/10.1007/s10208-012-9115-y

Premium Partner

    Bildnachweise