Search

International audience; Consider a square matrix with independent and identically distributed entries of zero mean and unit variance. It is well known that if the entries have a finite fourth moment, then, in high dimension, with high probability, the spectral radius is close to the square root of the dimension. We conjecture that this holds true under the sole assumption of zero mean and unit variance, in other words that there are no outliers in the circular law. In this work we establish the conjecture in the case of symmetrically distributed entries with a finite moment of order larger than two. The proof uses the method of moments combined with a novel truncation technique for cycle weights that might be of independent interest.

A simple connected non-regular graph is said to be (Formula presented.) -bidegreed, or biregular, if the vertices have degree from the set (Formula presented.) , with (Formula presented.). We consider two classes of (Formula presented.) -bidegreed graphs denoted by (Formula presented.) and (Formula presented.). A graph belongs to (Formula presented.) if: a) it is obtained from (Formula presented.) disjoint paths (Formula presented.) , (Formula presented.) , by identifying the vertices (Formula presented.) and the vertices (Formula presented.) , and the graph so obtained has n vertices; b) for each of the n vertices, pendant vertices are added, so that any vertex from any (Formula presented.) has degree (Formula presented.). The class (Formula presented.) , (Formula presented.) , is similarly obtained by identifying all the vertices (Formula presented.) and (Formula presented.) from the (Formula presented.) ’s, into a single vertex. In this paper, we show that for any graph in (Formula presented.) or (Formula presented.) , the spectral radius of the adjacency matrix increases whenever the difference between the lengths of any two (Formula presented.) ’s increases. We also compute some bounds for the spectral radius when the lengths of the (Formula presented.) ’s tend to infinity. Finally, we discuss about bicyclic (Formula presented.) -bidegreed graphs with n degree (Formula presented.) vertices minimizing the spectral radius. We prove that in most cases such graphs do not belong to (Formula presented.).

In this paper we consider bounded families F of complex n n-matrices. After introducing the concept of asymptotic order, we investigate how the norm of products of matrices behaves as the number of factors goes to infinity. In the case of defective families F ,u sing the asymptotic order allows us to get a deeper knowledge of the asymptotic behaviour than just considering the so-called generalized spectral radius. With reference to the well-known finiteness conjecture for finite families, we also introduce the concepts of spectrum-maximizing product and limit spectrum-maximizing product , showing that, for finite families of 2 2matrices, defectivity is equivalent to the existence of defective such limit products. © 2001 Elsevier Science Inc. All rights reserved.

Approximate backpropagation (ABP) methods have been used to identify the shape of axially symmetric acoustic scatterers in the resonance region from full aperture data [C1]. More recently one such method has been applied to the electromagnetic case [C2], where the Ipswich data [MK1] are available. ABP methods have relied on a heuristic relation between the expansion coefficients, which represent the scattered wave in the far zone and, respectively, on the obstacle boundary, $\Gamma$, and have led to minimization algorithms. In spite of satisfactory computational results, the well - posedness of ABP remains an open problem. A pertaining result, which may justify the method, is the following. Let $\lambda, \mu$ be multi-indices, $\{ v_{\mu} \}$ be e.g., the family of outgoing cylindrical (n = 2) wave functions and $\{ f_{\mu} \}:= {\bf f }$ be the sequence of far field scattering coefficients. Denote outward differentiation on $\Gamma$ by $\partial_N$. Assume both series $ \sum_{\mu} f_{\mu} v_{\mu} $, and $ \sum_{\mu} f_{\mu} \partial_N v_{\mu} $ converge uniformly on $ \Gamma $. Let $ {\bf b } $ be a sequence of inner products in $ L^2( \Gamma ) $, which depend on the incident wave, $ u $, and consider the operator $ {\cal R}{\bf L} := - (i/4)[ \langle u_{\lambda} |_{\Gamma} \partial_N v_{\mu} \rangle ] $, where $ u_{\lambda} := \real [v_{\lambda}] $. Also, let $ L $ be the approximation order and $ \Lambda [L] $ the corresponding set of indices. Denote e.g., by $ {\bf b}^{(L)} $ the finite sequence derived from $ {\bf b} $ and by $ {\bf c}^{(L)} $ the vector of least squares boundary coefficients, which solve $ || u + \sum_{\lambda \in \Lambda [L]} c_{\lambda}^{(L)} v_{\lambda}||_{L^2 (\Gamma)} ^2 = {\rm min} $. \textsc{Theorem}. Assume $ {\bf f}, {\bf b}\in \ell^2 $ and $ {\cal R}{\bf L} : \ell^2 \rightarrow \ell^2 $ is bounded. Let the spectral radius $ r_{\sigma} $ of $ {\cal R}{\bf L} $ satisfy $ r_{\sigma} < 1 $. Then a) $ \forall{\bf b}\in\ell^2 $ there exists a unique fixed point $ {\bf f} $ for the map $ {\bf p} [t+ l] = {\bf b} + {\cal R}{\bf L}\cdot{\bf p} [t], t = 0, 1, 2,... $, obtained by successive approximations, started with an arbitrary $ {\bf p}[0] \in\ell^2 $; b) let $ \bar{\bf c}^{(L)} $ be the fixed point of $ {\bf p}^{(L)} [ t+1] = {\bf b}^{(L)}+{\cal R}{\bf L}^{(L)}\cdot{\bf p}^{(L)}[ t ] $, with $ {\bf p}^{(L)}[0] \equiv {\bf c}^{(L)} $ and $ {\bf p}^{(L)}[ 1 ] = {\bf p}^{(L)} $; if $ | f_\lambda - \bar c_\lambda ^{(L)} | < \epsilon_1 | \bar c_\lambda ^{(L)} | $ and $ | c_\lambda ^{(L)} - \bar c_\lambda | - | p_\lambda ^{(L)} - \bar c_\lambda ^{(L)} | > 2 \epsilon_1 | \bar c_\lambda ^{(L)} |, \forall \lambda \in \Lambda [L] $ then forward propagation is effective i.e., $| f_\lambda ^{(L)} - p_\lambda ^{(L)} | < | f_\lambda ^{(L)} - c_\lambda ^{(L)} |, \forall \lambda \in \Lambda [L] $. These results will be applied to a class of numerical problems and their practical repercussions on shape identification will be discussed. References [Cl] G F CROSTA, The Backpropagation Method in Inverse Acoustics, in Tomography, Impedance Imaging and Integral Geometry, LAM 30 (Edited by M CHENEY, P KUCHMENT, E T QUINTO) pp 35 - 68, AMS: Providence, RI (1994). [C2] G F CROSTA, Scalar and Vector Backpropagation Applied to Shape Identification from Experimental Data: Recent Results and Open Problems to appear in Inverse Problems/Tomography and Image Processing, (Edited by A G Ramm) Plenum: New York, NY [MK1] R V McGahan, R E Kleinman, Special Session on Image Reconstruction Using Real Data, IEEE Antennas and Propagation Magazine 38 39 - 40 (1996)

The inverse electromagnetic problem for a perfectly conducting obstacle is stated in two spatial dimensions. Part One of the talk deals with the heuristics of shape reconstruction. Two classes of algorithms are presented, ABP and AFP. The former, known as the approximate back propagation algorithm, minimises the boundary defect; the latter, known as the approximate forward propagation algorithm, minimises the far-zone defect. Numerical results are provided for both. Part Two attempts at justifying the algorithms. The least-squares boundary coefficients are investigated in relation to error bounds and the Rayleigh hypothesis. The affine-least squares scheme is investigated in relation to the approximate forward propagator. The convergence of said propagator holds, provided the spectral radius of a Gram matrix is less than one.

Approximate backpropagation (ABP) methods have been used by the author to identify the shape of simple scatterers in the resonance region from full aperture data both in the acoustic and electromagnetic case. ABP methods rely on a relation between the expansion coefficients, which represent the scattered wave in the far zone and, respectively, on the obstacle boundary, $\Gamma$, and lead to minimization algorithms. In spite of satisfactory computational results, the well-posedness of ABP generally remains an open problem. A related result, which may eventually justify the method, pertains to a forward propagator i.e., to the affine map ${\bf N}[.]:= {\cal R}{\bf L} [.]+ {\bf b}$, which appears in the solution of the direct scattering problem. Very briefly, if both the scattered wave and its normal derivative on $\Gamma$ are represented by uniformly converging series according to a suitable basis in $L^2 (\Gamma)$, if ${\bf N}[.]$ is bounded and maps $\ell_2$ sequences of scattering coefficients into $\ell_2$ sequences and if the spectral radius $r_{\sigma [ {\cal R]{\bf L} ]$ satisfies $r_{\sigma [ {\cal R]{\bf L} ]

In this paper we direct attention at bounded families of complex n×n-matrices. In order to study their asymptotic behaviour, we recall from [Linear Algebra Appl. 322 (2001) 162] the concept of limit spectrum-maximizing product and show that nondefective families always admit such limit products. Then we consider defective families. In [loc. cite] we proved that, for finite families of 2×2-matrices, defectivity is equivalent to the existence of defective such limit products. This result led us to conjecture the validity of this property also for higher dimensions n 3. Here, instead, by making use of the results obtained by Bousch and Mairesse [J. Am. Math. Soc. 15 (2002) 77] that disproved the well-known Finiteness Conjecture, we find some counterexamples to our conjecture in [loc. cite] for all n 3. © 2002 Elsevier Science Inc. All rights reserved.