Página 1 dos resultados de 411 itens digitais encontrados em 0.006 segundos

Error Analysis of a Partial Pivoting Method for Structured Matrices

Sweet, Douglas R; Brent, Richard P
Fonte: Universidade Nacional da Austrália Publicador: Universidade Nacional da Austrália
Tipo: Working/Technical Paper Formato: 322757 bytes; 356 bytes; application/pdf; application/octet-stream
EN_AU
Relevância na Pesquisa
66.31%
Many matrices that arise in the solution of signal processing problems have a special displacement structure. For example, adaptive filtering and direction-of-arrival estimation yield matrices of Toeplitz type. A recent method of Gohberg, Kailath and Olshevsky (GKO) allows fast Gaussian elimination with partial pivoting for such structured matrices. In this paper, a rounding error analysis is performed on the Cauchy and Toeplitz variants of the GKO method. It is shown the error growth depends on the growth in certain auxiliary vectors, the generators, which are computed by the GKO algorithms. It is also shown that in certain circumstances, the growth in the generators can be large, and so the error growth is much larger than would be encountered with normal Gaussian elimination with partial pivoting. A modification of the algorithm to perform a type of row-column pivoting is proposed which may ameliorate this problem.; no

Blind channel identification and the eigenvalue problem of structured matrices

Ng, Michael K
Fonte: Universidade Nacional da Austrália Publicador: Universidade Nacional da Austrália
Tipo: Working/Technical Paper Formato: 267487 bytes; 356 bytes; application/pdf; application/octet-stream
EN_AU
Relevância na Pesquisa
46.08%
In this paper, we address the problem of restoring a signal from its noisy convolutions with two unknown channels. When the transfer functions of these two channels have no common factors, the blind channel identification problem can be solved by finding the minimum eigenvalue of the Toeplitz-like matrix and its corresponding eigenvector. We present a fast iterative algorithm to solve the numerical solution of the eigenvalue problem for these structured matrices and hence the channel coeficients can be estimated efficiently. Once the channel coefficients are available, they can be used to reconstruct the unknown signal. Preliminary numerical results illustrate the effectiveness of the method.; no

Fiedler matrices: numerical and structural properties

Pérez Álvaro, Javier
Fonte: Universidade Carlos III de Madrid Publicador: Universidade Carlos III de Madrid
Tipo: Tese de Doutorado
ENG
Relevância na Pesquisa
46.21%
The first and second Frobenius companion matrices appear frequently in numerical application, but it is well known that they possess many properties that are undesirable numerically, which limit their use in applications. Fiedler companion matrices, or Fiedler matrices for brevity, introduced in 2003, is a family of matrices which includes the two Frobenius matrices. The main goal of this work is to study whether or not Fiedler companion matrices can be used with more reliability than the Frobenius ones in the numerical applications where Frobenius matrices are used. For this reason, in this work we present a thorough study of Fiedler matrices: their structure and numerical properties, where we mean by numerical properties those properties that are interesting for applying these matrices in numerical computations, and some of their applications in the field on numerical linear algebra. The introduction of Fiedler companion matrices is an example of a simple idea that has been very influential in the development of several lines of research in the numerical linear algebra field. This family of matrices has important connections with a number of topics of current interest, including: polynomial root finding algorithms, linearizations of matrix polynomials...

Accurate solution of structured least squares problems via rank-revealing decompositions

Castro González, Nieves; Ceballos Cañón, Johan Armando; Martínez Dopico, Froilán C.; Molera, Juan M.
Fonte: Society for Industrial and Applied Mathematics Publicador: Society for Industrial and Applied Mathematics
Tipo: info:eu-repo/semantics/publishedVersion; info:eu-repo/semantics/article
Publicado em /07/2013 ENG
Relevância na Pesquisa
56.46%
Least squares problems min(x) parallel to b - Ax parallel to(2) where the matrix A is an element of C-mXn (m >= n) has some particular structure arise frequently in applications. Polynomial data fitting is a well-known instance of problems that yield highly structured matrices, but many other examples exist. Very often, structured matrices have huge condition numbers kappa(2)(A) = parallel to A parallel to(2) parallel to A(dagger)parallel to(2) (A(dagger) is the Moore-Penrose pseudoinverse of A) and therefore standard algorithms fail to compute accurate minimum 2-norm solutions of least squares problems. In this work, we introduce a framework that allows us to compute minimum 2-norm solutions of many classes of structured least squares problems accurately, i.e., with errors parallel to(x) over cap (0) - x(0)parallel to(2)/parallel to x(0)parallel to(2) = O(u), where u is the unit roundoff, independently of the magnitude of kappa(2)(A) for most vectors b. The cost of these accurate computations is O(n(2)m) flops, i.e., roughly the same cost as standard algorithms for least squares problems. The approach in this work relies in computing first an accurate rank-revealing decomposition of A, an idea that has been widely used in recent decades to compute...

Structured matrices and inverses

Comon, Pierre
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 16/03/2008
Relevância na Pesquisa
36.23%
A matrix (and any associated linear system) will be referred to as structured if it has a small displacement rank. It is known that the inverse of a structured matrix is structured, which allows fast inversion (or solution), and reduced storage requirements. According to two definitions of displacement structure of practical interest, it is shown here that several types of inverses are also structured, including the Moore-Penrose inverse of rank-deficient matrices.

Structured matrices, continued fractions, and root localization of polynomials

Holtz, Olga; Tyaglov, Mikhail
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
46.08%
We give a detailed account of various connections between several classes of objects: Hankel, Hurwitz, Toeplitz, Vandermonde and other structured matrices, Stietjes and Jacobi-type continued fractions, Cauchy indices, moment problems, total positivity, and root localization of univariate polynomials. Along with a survey of many classical facts, we provide a number of new results.; Comment: 79 pages; new material added to the Introduction

Distribution of Eigenvalues of Weighted, Structured Matrix Ensembles

Beckwith, Olivia; Luo, Victor; Miller, Steven J.; Shen, Karen; Triantafillou, Nicholas
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36.33%
The limiting distribution of eigenvalues of N x N random matrices has many applications. One of the most studied ensembles are real symmetric matrices with independent entries iidrv; the limiting rescaled spectral measure (LRSM) $\widetilde{\mu}$ is the semi-circle. Studies have determined the LRSMs for many structured ensembles, such as Toeplitz and circulant matrices. These have very different behavior; the LRSM for both have unbounded support. Given a structured ensemble such that (i) each random variable occurs o(N) times in each row and (ii) the LRSM exists, we introduce a parameter to continuously interpolate between these behaviors. We fix a p in [1/2, 1] and study the ensemble of signed structured matrices by multiplying the (i,j)-th and (j,i)-th entries of a matrix by a randomly chosen epsilon_ij in {1, -1}, with Prob(epsilon_ij = 1) = p (i.e., the Hadamard product). For p = 1/2 we prove that the limiting signed rescaled spectral measure is the semi-circle. For all other p, the limiting measure has bounded (resp., unbounded) support if $\widetilde{\mu}$ has bounded (resp., unbounded) support, and converges to $\widetilde{\mu}$ as p -> 1. Notably, these results hold for Toeplitz and circulant matrix ensembles. The proofs are by the Method of Moments. The analysis involves the pairings of 2k vertices on a circle. The contribution of each in the signed case is weighted by a factor depending on p and the number of vertices involved in at least one crossing. These numbers appear in combinatorics and knot theory. The number of configurations with no vertices involved in a crossing is well-studied...

Nearly Optimal Computations with Structured Matrices

Pan, Victor Y.; Tsigaridas, Elias
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 18/04/2014
Relevância na Pesquisa
46.38%
We estimate the Boolean complexity of multiplication of structured matrices by a vector and the solution of nonsingular linear systems of equations with these matrices. We study four basic most popular classes, that is, Toeplitz, Hankel, Cauchy and Van-der-monde matrices, for which the cited computational problems are equivalent to the task of polynomial multiplication and division and polynomial and rational multipoint evaluation and interpolation. The Boolean cost estimates for the latter problems have been obtained by Kirrinnis in \cite{kirrinnis-joc-1998}, except for rational interpolation, which we supply now. All known Boolean cost estimates for these problems rely on using Kronecker product. This implies the $d$-fold precision increase for the $d$-th degree output, but we avoid such an increase by relying on distinct techniques based on employing FFT. Furthermore we simplify the analysis and make it more transparent by combining the representation of our tasks and algorithms in terms of both structured matrices and polynomials and rational functions. This also enables further extensions of our estimates to cover Trummer's important problem and computations with the popular classes of structured matrices that generalize the four cited basic matrix classes.; Comment: (2014-04-10)

Efficient arithmetic operations for rank-structured matrices based on hierarchical low-rank updates

Börm, Steffen; Reimer, Knut
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
46.36%
Many matrices appearing in numerical methods for partial differential equations and integral equations are rank-structured, i.e., they contain submatrices that can be approximated by matrices of low rank. A relatively general class of rank-structured matrices are $\mathcal{H}^2$-matrices: they can reach the optimal order of complexity, but are still general enough for a large number of practical applications. We consider algorithms for performing algebraic operations with $\mathcal{H}^2$-matrices, i.e., for approximating the matrix product, inverse or factorizations in almost linear complexity. The new approach is based on local low-rank updates that can be performed in linear complexity. These updates can be combined with a recursive procedure to approximate the product of two $\mathcal{H}^2$-matrices, and these products can be used to approximate the matrix inverse and the LR or Cholesky factorization. Numerical experiments indicate that the new method leads to preconditioners that require $\mathcal{O}(n)$ units of storage, can be evaluated in $\mathcal{O}(n)$ operations, and take $\mathcal{O}(n \log n)$ operations to set up.

Some identities for determinants of structured matrices

Basor, Estelle L.; Ehrhardt, Torsten
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 09/08/2000
Relevância na Pesquisa
46.24%
In this paper we establish several relations between the determinants of the following structured matrices: Hankel matrices, symmetric Toeplitz + Hankel matrices and Toeplitz matrices. Using known results for the asymptotic behavior of Toeplitz determinants, these identities are used in order to obtain Fisher-Hartwig type results on the asymptotics of certain skewsymmetric Toeplitz determinants and certain Hankel determinants.

Symmetric Toeplitz-Structured Compressed Sensing Matrices

Huang, Tao; Fan, Yi-Zheng; Zhu, Ming
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 08/08/2013
Relevância na Pesquisa
36.26%
How to construct a suitable measurement matrix is still an open question in compressed sensing. A significant part of the recent work is that the measurement matrices are not completely random on the entries but exhibit considerable structure. In this paper, we proved that the symmetric Toeplitz matrix and its transforms can be used as measurement matrix and recovery signal with high probability. Compared with random matrices (e.g. Gaussian and Bernullio matrices) and some structured matrices (e.g. Toeplitz and circulant matrices), we need to generate fewer independent entries to obtain the measurement matrix while the effectiveness of recovery does not get worse. Furthermore, the signal can be recovered more efficiently by the algorithm.

Differential qd algorithm with shifts for rank-structured matrices

Zhlobich, Pavel
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
46.26%
Although QR iterations dominate in eigenvalue computations, there are several important cases when alternative LR-type algorithms may be preferable. In particular, in the symmetric tridiagonal case where differential qd algorithm with shifts (dqds) proposed by Fernando and Parlett enjoys often faster convergence while preserving high relative accuracy (that is not guaranteed in QR algorithm). In eigenvalue computations for rank-structured matrices QR algorithm is also a popular choice since, in the symmetric case, the rank structure is preserved. In the unsymmetric case, however, QR algorithm destroys the rank structure and, hence, LR-type algorithms come to play once again. In the current paper we discover several variants of qd algorithms for quasiseparable matrices. Remarkably, one of them, when applied to Hessenberg matrices becomes a direct generalization of dqds algorithm for tridiagonal matrices. Therefore, it can be applied to such important matrices as companion and confederate, and provides an alternative algorithm for finding roots of a polynomial represented in the basis of orthogonal polynomials. Results of preliminary numerical experiments are presented.

Theorems and counterexamples on structured matrices

Holtz, Olga
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 26/12/2005
Relevância na Pesquisa
46.21%
The subject of Chapter 1 is GKK $\tau$-matrices and related topics. Chapter 2 is devoted to boundedly invertible collections of matrices, with applications to operator norms and spline approximation. Various structured matrices (Toeplitz, Hessenberg, Hankel, Cauchy, and other) are used extensively throughout the thesis.; Comment: PhD thesis, University of Wisconsin-Madison, August 2000; 30 pages, 4 figures

Binary embeddings with structured hashed projections

Choromanska, Anna; Choromanski, Krzysztof; Bojarski, Mariusz; Jebara, Tony; Kumar, Sanjiv; LeCun, Yann
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 16/11/2015
Relevância na Pesquisa
36.42%
We consider the hashing mechanism for constructing binary data embeddings, that involves pseudo-random projections followed by nonlinear (sign function) mappings. The pseudo-random projection is described by a matrix, where not all entries are independent random variables but instead a fixed ''budget of randomness'' is distributed across the matrix. Such matrices can be efficiently stored in sub-quadratic or even linear space, provide reduction in randomness usage (i.e. number of required random values), and very often lead to computational speed ups. We prove several theoretical results showing that projections via various structured matrices followed by nonlinear mappings accurately preserve the angular distance between input high-dimensional vectors. To the best of our knowledge, these results are the first that give theoretical ground for the use of general structured matrices in the nonlinear setting. Thus, they significantly generalize previous extensions of the Johnson-Lindenstrauss lemma and prove the plausibility of the approach that was so far only heuristically confirmed for some special structured matrices. Consequently, we show that many structured matrices can be used as an efficient information compression mechanism. Our findings also build a better understanding of certain deep architectures...

Structured mapping problems for linearly structured matrices

Adhikari, Bibhas; Alam, Rafikul
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 10/09/2013
Relevância na Pesquisa
46.44%
Given an appropriate class of structured matrices S; we characterize matrices X and B for which there exists a matrix A \in S such that AX = B and determine all matrices in S mapping X to B. We also determine all matrices in S mapping X to B and having the smallest norm. We use these results to investigate structured backward errors of approximate eigenpairs and approximate invariant subspaces, and structured pseudospectra of structured matrices.; Comment: 15 pages

Error analysis of a partial pivoting method for structured matrices

Sweet, Douglas R.; Brent, Richard P.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 05/05/2010
Relevância na Pesquisa
46.21%
Many matrices that arise in the solution of signal processing problems have a special displacement structure. For example, adaptive filtering and direction-of-arrival estimation yield matrices of Toeplitz type. A recent method of Gohberg, Kailath and Olshevsky (GKO) allows fast Gaussian elimination with partial pivoting for such structured matrices. In this paper, a rounding error analysis is performed on the Cauchy and Toeplitz variants of the GKO method. It is shown the error growth depends on the growth in certain auxiliary vectors, the generators, which are computed by the GKO algorithms. It is also shown that in certain circumstances, the growth in the generators can be large, and so the error growth is much larger than would be encountered with normal Gaussian elimination with partial pivoting. A modification of the algorithm to perform a type of row-column pivoting is proposed; it may ameliorate this problem.; Comment: 18 pages. An old Technical Report, submitted for archival purposes. For further details see http://wwwmaths.anu.edu.au/~brent/pub/pub157.html

An efficient multi-core implementation of a novel HSS-structured multifrontal solver using randomized sampling

Ghysels, Pieter; Li, Xiaoye S.; Rouet, Francois-Henry; Williams, Samuel; Napov, Artem
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 25/02/2015
Relevância na Pesquisa
36.31%
We present a sparse linear system solver that is based on a multifrontal variant of Gaussian elimination, and exploits low-rank approximation of the resulting dense frontal matrices. We use hierarchically semiseparable (HSS) matrices, which have low-rank off-diagonal blocks, to approximate the frontal matrices. For HSS matrix construction, a randomized sampling algorithm is used together with interpolative decompositions. The combination of the randomized compression with a fast ULV HSS factorization leads to a solver with lower computational complexity than the standard multifrontal method for many applications, resulting in speedups up to 7 fold for problems in our test suite. The implementation targets many-core systems by using task parallelism with dynamic runtime scheduling. Numerical experiments show performance improvements over state-of-the-art sparse direct solvers. The implementation achieves high performance and good scalability on a range of modern shared memory parallel systems, including the Intel Xeon Phi (MIC). The code is part of a software package called STRUMPACK -- STRUctured Matrices PACKage, which also has a distributed memory component for dense rank-structured matrices.

Compressing rank-structured matrices via randomized sampling

Martinsson, Per-Gunnar
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 24/03/2015
Relevância na Pesquisa
46.29%
Randomized sampling has recently been proven a highly efficient technique for computing approximate factorizations of matrices that have low numerical rank. This paper describes an extension of such techniques to a wider class of matrices that are not themselves rank-deficient, but have off-diagonal blocks that are; specifically, the classes of so called \textit{Hierarchically Off-Diagonal Low Rank (HODLR)} matrices and \textit{Hierarchically Block Separable (HBS)} matrices. Such matrices arise frequently in numerical analysis and signal processing, in particular in the construction of fast methods for solving differential and integral equations numerically. These structures admit algebraic operations (matrix-vector multiplications, matrix factorizations, matrix inversion, etc.) to be performed very rapidly; but only once a data-sparse representation of the matrix has been constructed. How to rapidly compute this representation in the first place is much less well understood. The present paper demonstrates that if an $N\times N$ matrix can be applied to a vector in $O(N)$ time, and if the ranks of the off-diagonal blocks are bounded by an integer $k$, then the cost for constructing a HODLR representation is $O(k^{2}\,N\,(\log N)^{2})$...

Stable Manifold Embeddings with Structured Random Matrices

Yap, Han Lun; Wakin, Michael B.; Rozell, Christopher J.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36.23%
The fields of compressed sensing (CS) and matrix completion have shown that high-dimensional signals with sparse or low-rank structure can be effectively projected into a low-dimensional space (for efficient acquisition or processing) when the projection operator achieves a stable embedding of the data by satisfying the Restricted Isometry Property (RIP). It has also been shown that such stable embeddings can be achieved for general Riemannian submanifolds when random orthoprojectors are used for dimensionality reduction. Due to computational costs and system constraints, the CS community has recently explored the RIP for structured random matrices (e.g., random convolutions, localized measurements, deterministic constructions). The main contribution of this paper is to show that any matrix satisfying the RIP (i.e., providing a stable embedding for sparse signals) can be used to construct a stable embedding for manifold-modeled signals by randomizing the column signs and paying reasonable additional factors in the number of measurements. We demonstrate this result with several new constructions for stable manifold embeddings using structured matrices. This result allows advances in efficient projection schemes for sparse signals to be immediately applied to manifold signal models.

Structured inverse least-squares problem for structured matrices

Adhikari, Bibhas; Alam, Rafikul
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 10/01/2015
Relevância na Pesquisa
46.31%
Given a pair of matrices X and B and an appropriate class of structured matrices S, we provide a complete solution of the structured inverse least-squares problem $min_{A\in_S} \|AX-B\|_F$. Indeed, we determine all solutions of the structured inverse least squares problem as well as those solutions which have the smallest norm. We show that there are infi?nitely many smallest norm solutions of the least squares problem for the spectral norm whereas the smallest norm solution is unique for the Frobenius norm.; Comment: 10 pages. arXiv admin note: text overlap with arXiv:1309.2522