 Award ID(s):
 1838179
 NSFPAR ID:
 10206907
 Date Published:
 Journal Name:
 IEEE Statistical Signal Processing Workshop
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

The number of nonnegative integer matrices with given row and column sums features in a variety of problems in mathematics and statistics but no closedform expression for it is known, so we rely on approximations. In this paper, we describe a new such approximation, motivated by consideration of the statistics of matrices with noninteger numbers of columns. This estimate can be evaluated in time linear in the size of the matrix and returns results of accuracy as good as or better than existing lineartime approximations across a wide range of settings. We show that the estimate is asymptotically exact in the regime of sparse tables, while empirically performing at least as well as other lineartime estimates in the regime of dense tables. We also use the new estimate as the starting point for an improved numerical method for either counting or sampling matrices with given margins using sequential importance sampling. Code implementing our methods is available.more » « less

Spatially distributed networks of large size arise in a variety of science and engineering problems, such as wireless sensor networks and smart power grids. Most of their features can be described by properties of their statespace matrices whose entries have indices in the vertex set of a graph. In this paper, we introduce novel algebras of Beurling type that contain matrices on a connected simple graph having polynomial offdiagonal decay, and we show that they are Banach subalgebras of the space of all bounded operators on the space of all psummable sequences. The $\ell^p$stability of statespace matrices is an essential hypothesis for the robustness of spatially distributed networks. In this paper, we establish the equivalence among stabilities of matrices in Beurling algebras for different exponents $p$, with quantitative analysis for the lower stability bounds. Admission of normcontrol inversion plays a crucial role in some engineering practice. In this paper, we prove that matrices in Beurling subalgebras of have normcontrolled inversion and we find a normcontrolled polynomial with close to optimal degree. Polynomial estimate to powers of matrices is important for numerical implementation of spatially distributed networks. In this paper, we apply our results on normcontrolled inversion to obtain a polynomial estimate to powers of matrices in Beurling algebras. The polynomial estimate is a noncommutative extension about convolution powers of a complex function and is applicable to estimate the probability of hopping from one agent to another agent in a stationary Markov chain on a spatially distributed network.more » « less

In secondorder optimization, a potential bottleneck can be computing the Hessian matrix of the optimized function at every iteration. Randomized sketching has emerged as a powerful technique for constructing estimates of the Hessian which can be used to perform approximate Newton steps. This involves multiplication by a random sketching matrix, which introduces a tradeoff between the computational cost of sketching and the convergence rate of the optimization algorithm. A theoretically desirable but practically much too expensive choice is to use a dense Gaussian sketching matrix, which produces unbiased estimates of the exact Newton step and which offers strong problemindependent convergence guarantees. We show that the Gaussian sketching matrix can be drastically sparsified, significantly reducing the computational cost of sketching, without substantially affecting its convergence properties. This approach, called Newton LESS, is based on a recently introduced sketching technique: LEverage Score Sparsified (LESS) embeddings. We prove that NewtonLESS enjoys nearly the same problemindependent local convergence rate as Gaussian embeddings, not just up to constant factors but even down to lower order terms, for a large class of optimization tasks. In particular, this leads to a new stateoftheart convergence result for an iterative least squares solver. Finally, we extend LESS embeddings to include uniformly sparsified random sign matrices which can be implemented efficiently and which perform well in numerical experiments.more » « less

We demonstrate that with an optimally tuned scheduling function, adiabatic quantum computing (AQC) can readily solve a quantum linear system problem (QLSP) with O (κ poly(log (κ ε))) runtime, where κ is the condition number, and ε is the target accuracy. This is near optimal with respect to both κ and ε, and is achieved without relying on complicated amplitude amplification procedures that are difficult to implement. Our method is applicable to general nonHermitian matrices, and the cost as well as the number of qubits can be reduced when restricted to Hermitian matrices, and further to Hermitian positive definite matrices. The success of the timeoptimal AQC implies that the quantum approximate optimization algorithm (QAOA) with an optimal control protocol can also achieve the same complexity in terms of the runtime. Numerical results indicate that QAOA can yield the lowest runtime compared to the timeoptimal AQC, vanilla AQC, and the recently proposed randomization method.more » « less

Summary In this paper, we propose an efficient numerical scheme for solving some large‐scale ill‐posed linear inverse problems arising from image restoration. In order to accelerate the computation, two different hidden structures are exploited. First, the coefficient matrix is approximated as the sum of a small number of Kronecker products. This procedure not only introduces one more level of parallelism into the computation but also enables the usage of computationally intensive matrix–matrix multiplications in the subsequent optimization procedure. We then derive the corresponding Tikhonov regularized minimization model and extend the fast iterative shrinkage‐thresholding algorithm (FISTA) to solve the resulting optimization problem. Because the matrices appearing in the Kronecker product approximation are all structured matrices (Toeplitz, Hankel, etc.), we can further exploit their fast matrix–vector multiplication algorithms at each iteration. The proposed algorithm is thus called
structured FISTA (sFISTA). In particular, we show that the approximation error introduced by sFISTA is well under control and sFISTA can reach the same image restoration accuracy level as FISTA. Finally, both the theoretical complexity analysis and some numerical results are provided to demonstrate the efficiency of sFISTA.