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

## Error Analysis of a Partial Pivoting Method for Structured Matrices

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

Link permanente para citações:

## Blind channel identification and the eigenvalue problem of structured matrices

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

Link permanente para citações:

## Fiedler matrices: numerical and structural properties

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...

Link permanente para citações:

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

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%

#Accurate solutions#least squares problems#multiplicative perturbation theory#rank revealing decompositions#structured matrices#Moore–Penrose pseudoinverse.#Matemáticas

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...

Link permanente para citações:

## Structured matrices and inverses

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.

Link permanente para citações:

## Structured matrices, continued fractions, and root localization of polynomials

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Relevância na Pesquisa

46.08%

#Mathematics - Classical Analysis and ODEs#Mathematics - Complex Variables#Mathematics - History and Overview#Mathematics - Rings and Algebras#26-02, 26C10, 26C15, 26C05, 15-02, 15A23, 15B05, 15A15, 42C05

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

Link permanente para citações:

## Distribution of Eigenvalues of Weighted, Structured Matrix Ensembles

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...

Link permanente para citações:

## Nearly Optimal Computations with Structured Matrices

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)

Link permanente para citações:

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

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.

Link permanente para citações:

## Some identities for determinants of structured matrices

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.

Link permanente para citações:

## Symmetric Toeplitz-Structured Compressed Sensing Matrices

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.

Link permanente para citações:

## Differential qd algorithm with shifts for rank-structured matrices

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.

Link permanente para citações:

## Theorems and counterexamples on structured matrices

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 26/12/2005

Relevância na Pesquisa

46.21%

#Mathematics - Rings and Algebras#Mathematics - Classical Analysis and ODEs#15A48, 15A18, 15A57, 34D20, 93D05, 47B35, 41A15

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

Link permanente para citações:

## Binary embeddings with structured hashed projections

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...

Link permanente para citações:

## Structured mapping problems for linearly structured matrices

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

Link permanente para citações:

## Error analysis of a partial pivoting method for structured matrices

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 05/05/2010

Relevância na Pesquisa

46.21%

#Mathematics - Numerical Analysis#Computer Science - Numerical Analysis#65F05 (Primary) 15B05, 65G50 (Secondary)#F.2.1

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

Link permanente para citações:

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

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.

Link permanente para citações:

## Compressing rank-structured matrices via randomized sampling

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})$...

Link permanente para citações:

## Stable Manifold Embeddings with Structured Random Matrices

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.

Link permanente para citações:

## Structured inverse least-squares problem for structured matrices

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

Link permanente para citações: