Simple bounds for recovering low-complexity models

This note presents a unified analysis of the recovery of simple objects from random linear measurements. When the linear functionals are Gaussian, we show that an s-sparse vector in ${\mathbb{R}^n}$ can be efficiently recovered from 2s log n measurements with high probability and a rank r, n × n matrix can be efficiently recovered from r(6n ? 5r) measurements with high probability. For sparse vectors, this is within an additive factor of the best known nonasymptotic bounds. For low-rank matrices, this matches the best known bounds. We present a parallel analysis for block-sparse vectors obtaining similarly tight bounds. In the case of sparse and block-sparse signals, we additionally demonstrate that our bounds are only slightly weakened when the measurement map is a random sign matrix. Our results are based on analyzing a particular dual point which certifies optimality conditions of the respective convex programming problem. Our calculations rely only on standard large deviation inequalities and our analysis is self-contained.     

Normal Matrices and an Extension of Malyshev's Formula

Let A be a complex matrix of order n with n ≥ 3. We associate with A the 3n × 3n matrix $Q\left( {\gamma } \right) = \left( \begin{gathered} A \gamma _1 I_n \gamma _3 I_n \\ 0 A \gamma _2 I_n \\ 0 0 A \\ \end{gathered} \right)$ where $\gamma _1 ,\gamma _2 ,\gamma _3 $ are scalar parameters and γ=(γ₁,γ₂,γ₃). Let σ_i, 1 ≤ i ≤ 3n, be the singular values of Q(γ) in the decreasing order. We prove that, for a normal matrix A, its 2-norm distance from the set $\mathcal{M}$ of matrices with a zero eigenvalue of multiplicity at least 3 is equal to $\mathop {max}\limits_{\gamma _1 ,\gamma _2 \geqslant 0,\gamma _3 \in \mathbb{C}} \sigma _{3n - 2} (Q\left( \gamma \right)).$ This fact is a refinement (for normal matrices) of Malyshev's formula for the 2-norm distance from an arbitrary n × n matrix A to the set of n × n matrices with a multiple zero eigenvalue.     

Numerical algorithm for solving sesquilinear matrix equations of a certain class

A relationship is found between the solutions to the sesquilinear matrix equation X*DX + AX + X*B + C = 0, where all the matrix coefficients are n × n matrices, and the neutral subspaces of the 2n × 2n matrix \(M = \left( {\begin{array}{*{20}c} C & A \\ B & D \\ \end{array} } \right)\) . This relationship is used to design an algorithm for solving matrix equations of the indicated type. Numerical results obtained with the help of the proposed algorithm are presented.     

Parametric AE-solution sets to the parametric linear systems with multiple right-hand sides and parametric matrix equation A(p)X = B(p)

In this paper, the parametric matrix equation A(p)X = B(p) whose elements are linear functions of uncertain parameters varying within intervals are considered. In this matrix equation A(p) and B(p) are known m-by-m and m-by-n matrices respectively, and X is the m-by-n unknown matrix. We discuss the so-called AE-solution sets for such systems and give some analytical characterizations for the AE-solution sets and a sufficient condition under which these solution sets are bounded. We then propose a modification of Krawczyk operator for parametric systems which causes reduction of the computational complexity of obtaining an outer estimation for the parametric united solution set, considerably. Then we give a generalization of the Bauer-Skeel and the Hansen-Bliek-Rohn bounds for enclosing the parametric united solution set which also enables us to reduce the computational complexity, significantly. Also some numerical approaches based on Gaussian elimination and Gauss-Seidel methods to find outer estimations for the parametric united solution set are given. Finally, some numerical experiments are given to illustrate the performance of the proposed methods.     

Numerical algorithm for solving quadratic matrix equations of a certain class

A relationship is found between the solutions to the quadratic matrix equation X ^T DX + AX + X ^T B + C = 0, where all the matrix coefficients are n × n matrices, and the neutral subspaces of the 2n × 2n matrix \(M = \left( \begin{gathered} CA \\ BD \\ \end{gathered} \right) \) . This relationship is used to design an algorithm for solving matrix equations of the indicated type. Numerical results obtained with the help of the proposed algorithm are presented.     

A class of binary cyclic codes with five weights

In this paper, the dual code of the binary cyclic code of length 2 n-1 with three zeros α, α t 1 and α t 2 is proven to have five nonzero Hamming weights in the case that n 4 is even and t1 = 2 n/2 + 1, t2 = 2 n-1-2 n/2+1 + 1 or 2 n/2 + 3, where α is a primitive element of the finite field F 2 n . The dual code is a divisible code of level n/2+1, and its weight distribution is also completely determined. When n = 4, the dual code satisfies Ward's bound.     

Linear preservers of row-dense matrices

Let M_m,n be the set of all m × n real matrices. A matrix A ∈ M_m,n is said to be row-dense if there are no zeros between two nonzero entries for every row of this matrix. We find the structure of linear functions T: M_m,n → M_m,n that preserve or strongly preserve row-dense matrices, i.e., T(A) is row-dense whenever A is row-dense or T(A) is row-dense if and only if A is row-dense, respectively. Similarly, a matrix A ∈ M_n,m is called a column-dense matrix if every column of A is a column-dense vector. At the end, the structure of linear preservers (strong linear preservers) of column-dense matrices is found.     

Calculating the Isotropic Subspace of a Symmetric Quasi-Definite Matrix

Solutions to the sesquilinear matrix equation X*DX + AX + X*B + C = 0, where all matrices are of size n × n, are put in correspondence with n-dimensional neutral (or isotropic) subspaces of the associated matrix M of order 2n. A way of constructing such subspaces is proposed for when M is a symmetric quasi-definite matrix of the (n, n) type.     

Two stochastic models of a random walk in the U(n)-spherical duals of U(n + 1)

The random walk to be considered takes place in the δ-spherical dual of the group U(n + 1), for a fixed finite dimensional irreducible representation δ of U(n). The transition matrix comes from the three-term recursion relation satisfied by a sequence of matrix valued orthogonal polynomials built up from the irreducible spherical functions of type δ of SU(n + 1). One of the stochastic models is an urn model and the other is a Young diagram model.     

A fast approximation algorithm for the multicovering problem

The multicovering problem is: MIN cx subject to Ax≥b, xϵ{0, 1}ⁿ, where A is a matrix whose elements are all zero or one and b is a vector of positive integers. We present a fast heuristic for this important class of problems and analyze its worst-case performance: the ratio of the heuristic value to the optimum does not exceed the maximum row sum of the matrix A. The heuristic algorithm also provides a feasible dual solution vector that is useful in generating lower bounds on the value of the optimum.     

A new class of polynomial primal–dual methods for linear and semidefinite optimization

We propose a new class of primal–dual methods for linear optimization (LO). By using some new analysis tools, we prove that the large-update method for LO based on the new search direction has a polynomial complexity of O(n^4/(4+ρ)log(n/ε)) iterations, where ρ∈[0,2] is a parameter used in the system defining the search direction. If ρ=0, our results reproduce the well-known complexity of the standard primal–dual Newton method for LO. At each iteration, our algorithm needs only to solve a linear equation system. An extension of the algorithms to semidefinite optimization is also presented.     

Minimal paramount matrices

A real symmetric matrix of order n, n ? 2, is said to be paramount if each proper principal minor is not less than the absolute value of any other minor built from the same rows. A paramount matrix is minimal ¹ if reducing any of the diagonal entries removes the matrix from the paramount class. Minimal paramount matrices arise in the n-port realization problem of circuit theory. A condition is found that is equivalent to the minimality of a paramount matrix. Conditions are also found that guarantee that the inverse of an invertible minimal paramount matrix is itself minimal.     

Linear unbiased approximators of the disturbances in the standard linear model

The least squares residuals from the standard linear model have a variance matrix which is a function of the n × q matrix of observations on the regressors. We examine two classes of residuals which do not suffer from this defect. Our first class of residuals (LUZ residuals) has a variance matrix which is a scalar multiple of an n × n idempotent matrix of rank n ? q specified by the user, and our second class of residuals (LUS residuals) has a variance matrix which is a scalar multiple of the (n ? q)×(n ? q) identity matrix.     

Dual affine connections on a quadratic hyperband distribution in a projective-metric space and their applications

In this paper, we develop fundamentals of the dual theory of quadratic hyperband distributions H of m-dimensional line elements in a projective-metric space K _n (m < n ? 1). In particular, we show that, on a dual normalized distribution H, there are induced two dual affine connections and indicate some applications of these connections to the geometry of m-webs on H.     

A Note on MDS Codes, <Emphasis Type="Italic">n</Emphasis>-Arcs and Complete Designs

A generalized incidence matrix of a design over GF(q) is any matrix obtained from the (0, 1)-incidence matrix by replacing ones with nonzero elements from GF(q). The dimension d _q of a design D over GF(q) is defined as the minimum value of the q-rank of a generalized incidence matrix of D. It is proved that the dimension d _q of the complete design on n points having as blocks all w-subsets, is greater that or equal to n ? w + 1, and the equality d _q = n ? w + 1 holds if and only if there exists an [n, n ? w + 1, w] MDS code over GF(q), or equivalently, an n-arc in PG(w ? 2, q).     

A stability result using the matrix norm to bound the permanent

We prove a stability version of a general result that bounds the permanent of a matrix in terms of its operator norm. More specifically, suppose A is an n × n matrix over C (resp. R), and let P denote the set of n × n matrices over C (resp. R) that can be written as a permutation matrix times a unitary diagonal matrix. Then it is known that the permanent of A satisfies |per(A)| ≤ ||A|| ⁿ ₂ with equality iff A/||A||₂ ∈ P (where ||A||₂ is the operator 2-norm of A). We show a stability version of this result asserting that unless A is very close (in a particular sense) to one of these extremal matrices, its permanent is exponentially smaller (as a function of n) than ||A|| ⁿ ₂. In particular, for any fixed α, β > 0, we show that |per(A)| is exponentially smaller than ||A|| ⁿ ₂ unless all but at most αn rows contain entries of modulus at least ||A||₂(1?β).     

On <Emphasis Type="Italic">n</Emphasis>-cubic Pyramid Algebras

In this paper we study a class of algebras having n-dimensional pyramid shaped quiver with n-cubic cells, which we called n-cubic pyramid algebras. This class of algebras includes the quadratic dual of the basic n-Auslander absolutely n-complete algebras introduced by Iyama. We show that the projective resolutions of the simples of n-cubic pyramid algebras can be characterized by n-cuboids, and prove that they are periodic. So these algebras are almost Koszul and (n?1)-translation algebras. We also recover Iyama’s cone construction for n-Auslander absolutely n-complete algebras using n-cubic pyramid algebras and the theory of n-translation algebras.     

Numerical solution to generalized Lyapunov/Stein and rational Riccati equations in stochastic control

We consider the numerical solution of the generalized Lyapunov and Stein equations in \(\mathbb {R}^{n}\), arising respectively from stochastic optimal control in continuous- and discrete-time. Generalizing the Smith method, our algorithms converge quadratically and have an O(n³) computational complexity per iteration and an O(n²) memory requirement. For large-scale problems, when the relevant matrix operators are “sparse”, our algorithm for generalized Stein (or Lyapunov) equations may achieve the complexity and memory requirement of O(n) (or similar to that of the solution of the linear systems associated with the sparse matrix operators). These efficient algorithms can be applied to Newton’s method for the solution of the rational Riccati equations. This contrasts favourably with the naive Newton algorithms of O(n⁶) complexity or the slower modified Newton’s methods of O(n³) complexity. The convergence and error analysis will be considered and numerical examples provided.     

Lower bounds for the largest eigenvalue of the gcd matrix on {1, 2,..., n}

Consider the n×n matrix with (i, j)’th entry gcd (i, j). Its largest eigenvalue λ_n and sum of entries s_n satisfy λ_n > s_n/n. Because s_n cannot be expressed algebraically as a function of n, we underestimate it in several ways. In examples, we compare the bounds so obtained with one another and with a bound from S.Hong, R.Loewy (2004). We also conjecture that λ_n > 6π^?2nlogn for all n. If n is large enough, this follows from F.Balatoni (1969).