Search

Although the LLL algorithm 1 was originally developed for lattice basis reduction, the method can also be used 2 to reduce the condition number of a matrix. In this paper, we propose a pivoted LLL algorithm that further improves the conditioning. Our experimental results demonstrate that this pivoting scheme works well in practice.

This PDF file contains the front matter associated with SPIE Proceedings Volume 7074, including the Title Page, Copyright information, Table of Contents, and the Conference Committee listing.© (2008) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.

We examine a smugglers and border guards scenario. We place observers on a terrain so as to optimize their visible coverage area. Then we compute a path that a smuggler would take so as to avoid detection, while also minimizing the path length. We also examine how our results are affected by using a lossy representation of the terrain instead. We propose three new application-specific error metrics for evaluating terrain compression. Our target terrain applications are the optimal placement of observers on a landscape and the navigation through the terrain by smugglers. Instead of using standard metrics such as average or maximum elevation error, we seek to optimize our compression on the specific real-world application of smugglers and border guards.

The LLL algorithm is widely used to solve the integer least squares problems that arise in many engieeringapplications. As most practitioners did not understand how the LLL algorithm works, they avoided the issueby referring to the method as an integer Gram Schmidt approach (without explaining what they mean by thisterm). Luk and Tracy 1 were “rst to describe the behavior of the LLL algorithm, and they presented a newnumerical implementation that should be more robust than the original LLL scheme. In this paper, we comparethe numerical properties of the t wo dierent LLL implementations.Keywords: LLL algorithm, unimodular transformation, QR decomposition, reduced basis, Gauss transforma-tion, plane re”ection, numerical over”ow and under”ow. 1. INTRODUCTION The famous algorithm due to Lenstra, Lenstra and Lovasz 2 has many important applications; for example,wireless communication, cryptography, and GPS (see Hassibi and Vikalo 3 and references therein). In some ofthese applications, researchers use the LLL algorithm as a preconditioner in solvin g an integer least squaresproblem. Although the LLL algorithm is often referred to as an integer Gram-Schmidt procedure, no one hasexplained the workings of such a process. Luk and Tracy

The demand for digital maps continues to arise as mobile electronic devices become more popular nowadays. Instead of creating the entire map from void, we may convert a scanned paper map into a digital one. Color clustering is the very first step of the conversion process. Currently, most of the existing clustering algorithms are fully automatic. They are fast and efficient but may not work well in map conversion because of the numerous ambiguous issues associated with printed maps. Here we introduce two interactive approaches for color clustering on the map: color clustering with pre-calculated index colors (PCIC) and color clustering with pre-calculated color ranges (PCCR). We also introduce a memory model that could enhance and integrate different image processing techniques for fine-tuning the clustering results. Problems and examples of the algorithms are discussed in the paper.

Mobile devices use embedded processors with low computing capabilities to reduce power consumption. Since floating-point arithmetic units are power hungry, computationally intensive jobs must be accomplished with either digital signal processors or hardware co-processors. In this paper, we propose to perform fixed-point arithmetic on an integer hardware unit. We illustrate the advantages of our approach by implementing fingerprint verification on mobile devices.

AFastSingularValueAlgorithmforHankelMatricesFranklin T.LukaandSanzhengQiaobaDepartment of ComputerScienceandEngineeringChineseUniversityofHong KongShatin, NT,Hong KongbDepartment of Computing andSoftwareMcMasterUniversityHamilton, OntarioL8S4L7CanadaABSTRACTWe presentanO(n2log) algorithm for nding all the singular values of an-by-complex Hankel matrix.Keywords:Hankel matrix, singular values, Takagi decomp osition, Lanczos pro cess, complex-symmetric matrix.1.INTRODUCTIONStructured matrices play an imp ortant role in signal pro cessing.A common o ccurring structure is the Hankel form:H=0BBBBB@h12nh23n+1.....hn123hn+1211CCCCCA;where all elements along the same anti-diagonal are identical.There is an extensive literature on inverting HankelmatricesorsolvinglinearequationswithaHankelstructure;forgo o dlistofreferences,seeGolub-VanLoan.2The work is more limited on e cient eigenvalue computation for Hankel matrices; some examples are Cyb enko-VanLoan1, Luk-Qiao4and Trench5.In this pap er, we presentanO(n2log) algorithm for nding all the singular valuesofan-by-complex HankelmatrixH.Sp eci cally,we present an algorithm for computing the Takagi decomp osition (Horn-Johnson3):H=QT;(1)whereQis unitary and is diagonal with the singular values ofHon its diagonal.To our b est knowledge, this isthe rstO(n2log)singular value algorithm for Hankel matrices.Our pap er is organized as follows.A Lanczos tridiagonalization of a Hankel matrix is describ ed in Section 2, andatwo-by-toTakagi decomp osition inSection3.AQR metho dforthediagonalization oftridiagonal complex-symmetric matrix isgiven inSection 4,followed byanoverall algorithm andan illustrativenumerical example inSection 5.Notations.Weusethe\bar"symboltodenoteacomplexconjugate;forexample, M, vandcomplex conjugates of a matrixM,avectorvand a scalar, resp ectively.Sanzheng Qiao: Email: qiao@mcmaster.ca; Telephone:(905)525-9140 ext. 27234; Fax: (905)524-0340

algorithms for structured matrices are still under development. Cybenko and Van Loan2 proposed an algorithmfor computing the minimum eigenvalue of a symmetric positive definite Toeplitz matrix. Their algorithm is basedon the Levinson-Durbin Algorithm and Newton's method and requires at most 0(n2) floating-point operations perNewton iteration and heuristically O(logn) iterations. Building on their work2 Trench5 presented an algorithm forHermitian Toeplitz matrices. His algorithm requires 0(n2) operations per eigenvalue-eigenvector pair. In this paper,we study the eigenvalue problem of a Hankel matrix. Taking advantage of two properties, namely that a complexHankel matrix is symmetric and that a permuted Hankel matrix can be embedded in a circulant matrix, we developan 0 (n2 log n) algorithm to find all the eigenvalues of an n x n Hankel matrix.Our paper is organized as follows. How to exploit complex-symmetry is presented in Section 2, and how toconstruct complex-orthogonal rotations in Section 3. An O(nlogn) scheme for multiplying a Hankel matrix and a

We present a new algorithm for finding specially structured vectors that span a null space. These vectors arise in direction finding applications for uniform rectangular antenna arrays.

In this paper, we propose the use of complex-orthogonal transformations for finding the eigenvalues of a complex symmetric matrix. Using these special transformations can significantly reduce computational costs because the tridiagonal structure of a complex symmetric matrix is maintained.

In array processing, one technique for cancelling interference in the presence of colored noise is the ULLV decomposition of a pair of matrices. The factorization is stable and accurate, and is easy to update when a row is added to either one of the two matrices. In earlier work, we made the assumptions that both matrices must have at least as many rows as columns and that the matrix representing interference must have full column rank. In this paper, we relax the latter restriction and allow the interference matrix to be rank deficient. We present an algorithm for computing the decomposition and two techniques for updating it. The details on updating are quite different from those in the full rank case.

In signal and image processing, regularization often requires a rank-revealing decomposition of a symmetric Toeplitz matrix with a small rank deficiency. In this paper, we present an efficient factorization method that exploits symmetry as well as the rank and Toeplitz properties of the given matrix.

The ill-conditioned nature of the inverse problem of image restoration produces dramatic consequences when the boundaries of the image are incorrectly modeled. Solutions to this problem are difficult to find in the literature. In this paper, we develop and analyze two sets of new approaches that are effective with algebraic restoration procedures.

Despite its important signal processing applications, the generalized singular value decomposition (GSVD) is under-utilized due to the high updating cost. In this paper, we consider the noise subspace problem and introduce a new approximate GSVD that is easily amenable to updating.

In tins paper, we propose a method for computing the SVD of a product of two 2 x 2 triangular matrices. We show that our method is numerically desirable in that all relevant residual elements will be numerically small.

The problem of linearly constrained least squares has many applications in signal processing. In this paper, we present a perturbation analysis of a novel, linearly constrained least squares algorithm for adaptive beamforming. The perturbation bounds for the solution as well as for the latest residual element are derived. We also propose an error estimation scheme for the residual element. This error estimation scheme can be incorporated into a systolic array implementation of the algorithm. The additional time required for error estimation is small, as we show how the processor idle time can be used to carry out almost all the calculations.

We present a simple matrix representation of the Berlekamp-Massey algorithm for solving a Hankel system of linear equations, and we show how pivoting can be added to the algorithm to improve numerical accuracy of the method.© (1991) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.

We present an algorithm that can detect and isolate a single passive antenna failure under the assumption of slowly time varying signal sources. Our failure detection algorithm recursively computes an eigenvalue decomposition of the covariance of the "syndrome" vector. The sensor failure is detected using the largest eigenvalue, and the faulty sensor is located using the corresponding eigenvector. The algorithm can also be used in conjunction with existing singular value decomposition or orthogonal triangularization based recursive antenna array processing methods.

In this paper we propose a new algorithm for computing a singular value decomposition of a matrix product. We show that our algorithm is numerically desirable in that all relevant residual elements will be numerically small.© (1990) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.

Systolic architectures for eigenvalues and singular values are discussed. One "triangular" processor array and associated algorithms for computing the QR-decomposition, the singular value decomposition, the generalized singular value decomposition and the CS-decomposition are described in detail.

Four matrix operations: matrix multiplication, the QR decomposition, the singular value decomposition, and the generalized singular value decomposition, form the basic tools for modern signal processing. This paper discusses their implementation on the 65,536-processor Connection Machine, and presents results showing that for n X n matrices, where n

The weighted checksum scheme has been proposed as a low-cost error detection procedure for parallel matrix computations. Error correction has proved to be a much more difficult problem to solve than detection when using weighted checksums. In this paper we provide a theoretical basis for the correction problem. We show that for a distance d+1 weighted checksum scheme, if a maximum of ici [d/2] errors ensue then we can determine exactly how many errors have occurred. We further show that in this case we can correct the errors and give a procedure for doing so.

This paper contains the computation of the singular value decomposition using systolic arrays. Two different linear time algorithms are presented.

Linear time computation of the singular value decomposition (SVD) would be useful in many real time signal processing applications. Two algorithms for the SVD have been developed for implementation on a quadratic array of processors. A specific architecture is proposed and we demonstrate the mapping of the algorithms to the architecture. The algorithms and architecture together have been verified by functional level and register transfer level simulation.

Present work is discussed on the implementation of system identification and control methods using singular value decompositions (SVD) on a systolic array of INMOS Transputer chips. The central computation required for both the system identification and control is a canonical variate analysis involving the computation of a generalized singular value decomposition (GSVD). Algorithms are developed for efficient computation of the GSVD on the Transputer systolic array. The GSVD algorithm is developed with particular attention given to the numerical stability, accuracy, and computational efficiency on the systolic array. The implementation of the software in Occam for an array of INMOS transputers is discussed in terms of granularity, required memory, and computation time.

Architectures for systolic array processor elements for calculating the singular value decomposition (SVD) are proposed. These special purpose VLSI structures incorporate the coordinate rotation (coRDic) algorithms to diagonalize 2X 2 submatrices of a large array. The area-time complexity of the proposed architectures is analyzed along with topics related to a prototype implementation.

Existing fault tolerance schemes have often been ignored by systolic array designers because they are too costly and unwieldy to implement. With this in mind, we have developed a new technique specially tailored for recursiveleast squares minimization that emphasizes simplicity. We propose a new decoding scheme that allows for errordetection while wasting no precious processor cycles and preserving the basic structure of the systolic array. We willshow that errors can be detected by examining a single scalar. The technique can be implemented with negligible algorithmic modification and little additional hardware. The simplicity of our method invites its use in future systolicarrays. 1. INTRODUCTIONThe compatibility of systolic arrays and algorithms with both matrix computations and today's VLSI and wafer -scale technology guarantees their future use as key components in any signal processing system. An especially important systolic algorithm is the QR matrix decomposition for least squares minimization, a crucial cog in mostadaptive antenna processing algorithms. The importance of these problems is evidenced by the two major systolicarray projects; one at MIT's Lincoln Laboratory [1] and the other at England's Royal Signals and Radar Establish

A new class of algorithms based upon a generalized singular value decomposition (SVD) is considered for system identification, statistical model order determination, model order reduction, and predictive control. Currently available algorithms for system identification and control are not completely reliable for automatic implementation on microprocessors in real time. In the generalized SVD approach, the algorithms are computationally stable and numerically accurate and can be implemented on systolic array processors using recently developed algorithms resulting in a considerable speedup. The method is based upon a recent generalized canonical variate analysis (CVA) method for determining the optimal state of a restricted order in system identification, reduced order stochastic filtering, and model predictive control. This permits a unified approach to the solution of these problems from the viewpoints of a prediction problem as well as an approximation problem. Algorithms for online computation in identification, filtering, and control of high order linear multivariable systems are developed. Implementing these algorithms on systolic array processors are discussed.

In this paper, we study three fault tolerance techniques: data redundancy, algorithm-based fault tolerance, and pair and spare. These techniques, each individually useful, produce excitingly high levels of protection at a relatively low cost when used in combination. We first discuss the techniques separately, extending triple data redundancy to band matrix multiplication while applying algorithm-based fault tolerance to dense matrix multiplication. We then combine double data redundancy and algorithm-based fault tolerance to produce a linear array that corrects transient errors at minimal costs. Finally, we show how the above techniques can be used to implement pair and spare at half the normal cost.

A fault tolerant systolic processor system is proposed for computing the singular value decomposition of an nxn matrix. This approach uses only orthogonal interconnections and simple multiply and accumulate processors in the array. The fault tolerant properties are achieved through a composite of simple low overhead structures. The square root computations, and all fault tolerance computations are performed in one highly pipelined boundary processor. The architecture requires 0(n) processors and 0(n2 log n) time.