|M.Sc Student||Steinberg Daureen|
|Subject||Computation of Matrix Norms with Applications to Robust|
|Department||Department of Industrial Engineering and Management||Supervisor||Professor Arkadi Nemirovski|
The research is devoted to investigating the problem of computing the norm ||A||E,F=max||Ax||F: xєE,||x||E≤1of linear mapping x→Ax, acting from a finite dimensional normed space (E,|| . ||E) to a finite dimensional normed space (F,|| . ||F). We focused on the case where (E,|| . ||E) = (Rn,|| . ||p) and (F,|| . ||F)= (Rm,|| . ||r), so that A can be identified with an m X n matrix; the associated norm ||A||E,F is denoted by ||A||p,r. In our research we proved that ||A||p,r is NP hard in the case when 1 ≤ r < p ≤ ∞ - this results coincides with our conjecture that the only easy cases to compute ||A||p,r are when (p=1, 1 ≤ r ≤∞), (r=∞, 1 ≤ p ≤ ∞), (p=r=2). We also refine Nestrov’s theorem by showing that the quantity of the upper bound placed by semidefinite relaxation on ||A||p,r in the case of
1≤ r ≤ 2 ≤ p ≤ ∞, is much less conservative in a wide range of values of p,r than the 2.29 factor suggested by Nestrov. Finally we develop a simple interpolation technique allowing to extend the efficiently upper bound on ||A||p,r from its original domain to the entire range of p ≥ 1, r ≥ 1 and we showed that the extended bound is tight within a factor depending on p,n,r,m and never exceeding O(1)(max(m,n))25/128. Our analysis demonstrates that this factor does not exceed 9.48 for all p,r, provided that m,n≤100,000.