Computing the block factorization of complex Hankel matrices

In this paper, we present an algorithm for finding an approximate block diagonalization of complex Hankel matrices. Our method is based on inversion techniques of an upper triangular Toeplitz matrix, specifically, by simple forward substitution. We also consider an approximate block diagonalization of complex Hankel matrices via Schur complementation. An application of our algorithm by calculating the approximate polynomial quotient and remainder appearing in the Euclidean algorithm is also given. We have implemented our algorithms in Matlab. Numerical examples are included. They show the effectiveness of our strategy.     

The number of minimally connected block designs

The formula a^b−1b^a−1 is derived for the number of connected a × b block designs having the least possible number, a + b − 1, of observations needed for connectedness. It is shown that this formula also arises as the number of labeled bicolored trees with a vertices of one color and b vertices of the other.     

Alternating optimization to solve penalized regression‐based clustering model

Two previously proposed heuristic algorithms for solving penalized regression‐based clustering model (PRClust) are (a) an algorithm that combines the difference‐of‐convex programming with a coordinate‐wise descent (DC‐CD) algorithm and (b) an algorithm that combines DC with the alternating direction method of multipliers (DC‐ADMM). In this paper, a faster method is proposed for solving PRClust. DC‐CD uses p × n × (n ? 1)/2 slack variables to solve PRClust, where n is the number of data and p is the number of their features. In each iteration of DC‐CD, these slack variable and cluster centres are updated using a second‐order cone programming (SOCP). DC‐ADMM uses p × n × (n ? 1) slack variables. In each iteration of DC‐ADMM, these slack variables and cluster centres are updated using ADMM. In this paper, PRClust is reformulated into an equivalent model to be solved using alternating optimization. Our proposed algorithm needs only n × (n ? 1)/2 slack variables, which is much less than that of DC‐CD and DC‐ADMM and updates them analytically using a simple equation in each iteration of the algorithm. Our proposed algorithm updates only cluster centres using an SOCP. Therefore, our proposed SOCP is much smaller than that of DC‐CD, which is used to update both cluster centres and slack variables. Experimental results on real datasets confirm that our proposed method is faster and much faster than DC‐ADMM and DC‐CD, respectively.     

On the convergence of the Bl-LSQR algorithm for solving matrix equations

Karimi and Toutounian [The block least squares method for solving nonsymmetric linear system with multiple right-hand sides, Appl. Math. Comput. 177 (2006), pp. 852–862], proposed a block version of the LSQR algorithm, say Bl-LSQR, for solving linear system of equations with multiple right-hand sides. In this paper, the convergence of the Bl-LSQR algorithm is studied. We deal with some computational aspects of the Bl-LSQR algorithm for solving matrix equations. Some numerical experiments on test matrices are presented.     

一类可分离SAT问题的O(1.890n)精确算法

布尔可满足性问题（SAT）是指对于给定的布尔公式,是否存在一个可满足的真值指派.这是第1个被证明的NP完全问题,一般认为不存在多项式时间算法,除非P=NP.学者们大都研究了子句长度不超过k的SAT问题（k-SAT）,从全局搜索到局部搜索,给出了大量的相对有效算法,包括随机算法和确定算法.目前,最好算法的时间复杂度不超过O（（2-2/k）ⁿ）,当k=3时,最好算法时间复杂度为O（1.308ⁿ）.而对于更一般的与子句长度k无关的SAT问题,很少有文献涉及.引入了一类可分离SAT问题,即3-正则可分离可满足性问题（3-RSSAT）,证明了3-RSSAT是NP完全问题,给出了一般SAT问题3-正则可分离性的O（1.890ⁿ）判定算法.然后,利用矩阵相乘算法的研究成果,给出了3-RSSAT问题的O（1.890ⁿ）精确算法,该算法与子句长度无关.     

块截断编码的图像自嵌入半脆弱水印算法

目的 数字图像自嵌入水印技术是解决图像篡改检测和恢复问题的主要技术手段之一,现有的自嵌入水印技术存在着认证粒度不高、嵌入水印后的图像失真较大,且无法抵抗滤波等操作。为提高图像自嵌入水印的认证粒度以及抵抗滤波等处理操作的能力,提出了一种基于块截断编码的图像自嵌入半脆弱水印算法。方法 水印生成与嵌入：首先,将图像进行块级别的二级划分,分别生成粒度为4×4和2×2的图像块;然后,利用块截断编码对每个4×4图像块进行压缩编码,生成2×2图像块的恢复水印,并对恢复水印进行哈希生成2×2图像块的认证水印;最后,将恢复水印和认证水印级联构成自嵌入水印,嵌入到映射块中。篡改认证与恢复：首先,将某个4×4图像块提取的水印与该块生成的水印比较,判别该图像块的2×2子块是否通过认证;最后,依据认证结果对2×2图像块实施恢复。结果 该算法产生的水印图像的峰值信噪比（peak signal-to-noise ratio,PSNR）均高于44 dB,在50%的篡改率下,恢复后的图像质量可达到32.7 dB。该算法生成水印并在图像上嵌入大约需要3.15 s,恢复图像大约需要3.6 s。结论 算法利用块截断编码,有效缩短了生成的水印长度,保证嵌入水印后图像的质量。此外,通过引入的可容忍修改阈值,使得水印能够对滤波等图像处理操作具有一定的鲁棒性,同时保证对图像的恶意篡改具有敏感性。最后通过与最近典型方法的对比实验,验证了算法在嵌入水印后图像质量、恢复图像质量等方面的优势。     

Global robust stabilization of nonlinear systems subject to input constraints

Our main purpose in this paper is to further address the global stabilization problem for affine systems by means of bounded feedback control functions, taking into account a large class of control value sets: p, r ‐weighted balls ??^m _r (p), with 1<p?∞, defined via p, r ‐weighted gauge functions. Observe that p=∞ is allowed, so that m‐dimensional r ‐hyperboxes ??^m _r (∞)?[?r₁^?,r₁⁺]×???×[?r_m^?,r_m⁺], r_j^±>0 are also considered. Working along the line of Artstein–Sontag's approach, we construct an explicit formula for a one‐parameterized family of continuous feedback controls taking values in ?? _r ^m(p) that globally asymptotically stabilize an affine system, provided an appropriate control Lyapunov function is known. The designed family of controls is suboptimal with respect to the robust stability margin for uncertain systems. The problem of achieving disturbance attenuation for persistent disturbances is also considered. Copyright © 2002 John Wiley & Sons, Ltd.     

A stochastic realization algorithm via block LQ decomposition in Hilbert space

A stochastic realization problem of a stationary stochastic process is re-visited, and a new stochastically balanced realization algorithm is derived in a Hilbert space generated by second-order stationary processes. The present algorithm computes a stochastically balanced realization by means of the singular value decomposition of a weighted block Hankel matrix derived by a “block LQ decomposition”. Extension to a stochastic subspace identification method explains how the proposed abstract algorithm is implemented in system identification.     

Parametric Solutions to the Generalized Discrete Yakubovich‐Transpose Matrix Equation

This paper is concerned with the complete parametric solutions to the generalized discrete Yakubovich‐transpose matrix equation X − AX^TB = CY. which is related with several types of matrix equations in control theory. One of the parametric solutions has a neat and elegant form in terms of the Krylov matrix, a block Hankel matrix and an observability matrix. In addition, the special case of the generalized discrete Yakubovich‐transpose matrix equation, which is called the Karm‐Yakubovich‐transpose matrix equation, is considered. The explicit solutions to the Karm‐Yakubovich‐transpose matrix equation are also presented by the so‐called generalized Leverrier algorithm. At the end of the paper, two examples are given to show the efficiency of the proposed algorithm.     

求分块周期三对角矩阵逆矩阵的新算法

根据分块三对角矩阵逆矩阵的特殊结构,利用其LU和UL分解,并使用Sheman-Morrison-Woodbury公式,得到一个求分块周期三对角矩阵逆矩阵的新算法,并由该算法得到求周期三对角矩阵和对称周期三对角矩阵逆矩阵的新算法。新算法比传统算法的计算复杂度和计算时间要低。     

两元指纹向量聚类问题的复杂性与改进启发式算法

证明丢失值位数不超过2的指纹向量聚类问题为NP-Hard,并给出Figueroa等人指纹向量聚类启发式算法的改进算法.主要改进了算法的实现方法.以链表存储相容顶点集合,并以逐位扫描指纹向量的方法产生相容点集链表,可将产生相容点集的时间复杂性由O(m·n·2p)减小为O(m·(n·p 1)·2p),可使划分一个唯一极大团或最大团的时间复杂性由O(m·p·2p)减小为O(m·2p).实际测试显示,改进算法的空间复杂性平均减少为原算法的49%以下,平均可用原算法20%的时间求解与原算法相同的实例.当丢失值位数超过6时,改进算法几乎总可用不超过原算法11%的时间计算与原算法相同的实例.     

Bounds on the Diameter of One-Dimensional Pec Networks

The diameter of a packed exponential connections (PEC) network on N nodes is shown to be Θ([formula] × [formula]).⁴ A routing algorithm which can route between any two nodes in O([formula] × [formula]) steps is shown. A methodology to find a set of links to be used by a shortest path from node 1 to node N − 1 is derived. We also show that semigroup operations can be performed in O([formula] × [formula]) parallel steps.     

图像分区选择的像素值排序可逆数据隐藏

目的 基于像素值排序（PVO）的数据隐藏算法因其高保真的优越性受到广泛重视,并不断得到改进。本文提出一种图像分区选择思想,以进一步充分利用图像的嵌入空间,改善PVO算法的嵌入性能,提高载秘图像的信噪比。方法 原始PVO算法通常采用预测差值“1”进行数据隐藏,对平滑像素组有较好的利用率和隐蔽性,而对毛躁像素组隐秘性能明显下降,算法性能与图像像素分布情况密切相关。本文在PVO算法基础上提出图像分区选择的思想,首先,将原始图像分为若干区域,然后按移位率从小到大的顺序依次选择图像区域;其次,在每个区域中选择合适的嵌入预测误差;最后,按顺序在被选区域利用该区域的最优嵌入差值完成信息嵌入。结果 假设将图像划分为8×8个区域,对本文算法与原始PVO算法进行比较,当嵌入量为1×10⁴ bit时,Elaine图像的移位率由81.59%降为74.40%,载秘图像的峰值信噪比（PSNR）值由55.388 2提高为56.996 9,提高了1.608 7,采用其他图像并就不同嵌入量进行实验,各图像PSNR值均表现出不同程度的提高。其次,将图像分别划分为2×2、4×4、8×8、16×16个分区,当嵌入量为1×10⁴ bit时,Lena图像PSNR由原始PVO的59.204 6逐渐增加至60.846 9,其他图像在不同嵌入量时PSNR均随着分区数的增加而有不同程度的提高。结论 本文提出的基于图像分区选择的改进PVO算法,可根据像素分布情况增加对嵌入空间的利用,在相同嵌入量情况下,改进后的算法能够获得更高的PSNR值;在一定分区数量条件范围内,分区数量与图像PSNR值表现出正相关性,随着分区数量的增加,图像PSNR值随之增加;本文方法在一定程度上改善了嵌入容量,弥补了因分区数量增加带来的辅助信息增加的问题。     

On a class of generalized eigenvalue problems and equivalent eigenvalue problems that arise in systems and control theory

Systems and control theory has long been a rich source of problems for the numerical linear algebra community. In many problems, conditions on analytic functions of a complex variable are usually evaluated by solving a special generalized eigenvalue problem. In this paper we develop a general framework for studying such problems. We show that for these problems, solutions can be obtained by either solving a generalized eigenvalue problem, or by solving an equivalent eigenvalue problem. A consequence of this observation is that these problems can always be solved by finding the eigenvalues of a Hamiltonian (or discrete-time counterpart) matrix, even in cases where an associated Hamiltonian matrix, cannot (normally) be defined. We also derive a number of new compact tests for determining whether or not a transfer function matrix is strictly positive real. These tests, which are of independent interest due to the fact that many problems can be recast as SPR problems, are defined even in the case when the matrix D+D^∗ is singular, and can be formulated without requiring inversion of the system matrix A.     

Admissible factorizations of Hankel operators induce well-posed linear systems

One of the basic axioms of a well-posed linear system says that the Hankel operator of the input–output map of the system factors into the product of the input map and the output map. Here we prove the converse: every factorization of the Hankel operator of a bounded causal time-invariant map from L² to L² which satisfies a certain admissibility condition induces a stable well-posed linear system. In particular, there is a one-to-one correspondence between the set of all minimal stable well-posed realizations of a given stable causal time-invariant input–output map (or equivalently, of a given H^∞ transfer function) and all minimal stable admissible factorizations of the Hankel operator of this input–output map.     

Numerical evaluation of Hankel transforms using Haar wavelets

The aim of the article is to find an efficient algorithm for local numerical evaluation of F _n (p) by expressing the corresponding finite Hankel transform [Fcirc] _n (p) in Haar series and truncating it.     

Fast Parallel Algorithms for Solving Triangular Systems of Linear Equations on the Hypercube

This paper presents efficient hypercube algorithms for solving triangular systems of linear equations by using various matrix partitioning and mapping schemes. Recently, several parallel algorithms have been developed for this problem. In these algorithms, the triangular solver is treated as the second stage of Gauss elimination. Thus, the triangular matrix is distributed by columns (or rows) in a wrap fashion since it is likely that the matrix is distributed this way after an LU decomposition has been done on the matrix. However, the efficiency of the algorithms is low. Our motivation is to develop various data partitioning and mapping schemes for hypercube algorithms by treating the triangular solver as an independent problem. Theoretically, the computation time of our best algorithm is ((12p + 1)n² + 36p³ − 28p²)/(24p²), and an upper bound on the communication time is 2αp log p (log n − log p) + 2α(log n − log p − 1) log p + (cn/p − 2c)(2 log p − 1) + log p(cn − c − α), where α is the (communication startup time)/(one entry scanning time), c is a constant, n is the order of the triangular system and p is the number of nodes in the hypercube. Experimental results show that the algorithm is efficient. The efficiency of the algorithm is 0.945 when p = 2, n = 513, and 0.93 when p = 8, n = 1025.     

A TENSOR-THEORETIC ENHANCEMENT TO THE HILL CIPHER SYSTEM

The Hill matrix algorithm[3], published in 1929, is known for being the first purely algebraic cryptographic system and for starting the entire field of algebraic cryptology. In this paper, an operator derived from ring isomorphism theory is adapted for use in the Hill system which greatly increases the block size that a matrix can encrypt; specifically, a k×k invertible matrix over Z _n represents an invertible matrix of order k ³, which produces ciphertext blocks k ²-times as long as the original matrix could. This enhancement increases the Hill system's security considerably.