ML p(r)ior | Interval Linear Algebra and Computational Complexity

### Interval Linear Algebra and Computational Complexity

2016-02-01
1602.00349 | cs.CC
This work connects two mathematical fields - computational complexity and interval linear algebra. It introduces the basic topics of interval linear algebra - regularity and singularity, full column rank, solving a linear system, deciding solvability of a linear system, computing inverse matrix, eigenvalues, checking positive (semi)definiteness or stability. We discuss these problems and relations between them from the view of computational complexity. Many problems in interval linear algebra are intractable, hence we emphasize subclasses of these problems that are easily solvable or decidable. The aim of this work is to provide a basic insight into this field and to provide materials for further reading and research.

Highlights - Most important sentences from the article

# Related Articles

2017-01-08
1701.01994 | cs.SC

Differential (Ore) type polynomials with "approximate" polynomial coefficients are introduced. These… show more

Highlights - Most important sentences from the article

2017-12-18
1712.06309 | math.OC

In this paper, we present FPT-algorithms for special cases of the shortest lattice vector, integer l… show more

Highlights - Most important sentences from the article

2019-03-15
1903.10272 | math.NA

The work is devoted to the development of numerical methods for computing "formal solutions" of inte… show more

Highlights - Most important sentences from the article

2017-01-23
1701.06386 | cs.CC

Weighted counting problems are a natural generalization of counting problems where a weight is assoc… show more

Highlights - Most important sentences from the article

2017-08-11
1708.03495 | cs.DS

We consider two basic algorithmic problems concerning tuples of (skew-)symmetric matrices. The first… show more

Highlights - Most important sentences from the article

2018-06-04
1806.01050 | cs.IT

In this work, we study the computational complexity of the Minimum Distance Code Detection problem. … show more

Highlights - Most important sentences from the article

2019-04-02
1904.01182 | cs.CC

We study the problem of constructing explicit families of matrices which cannot be expressed as a pr… show more

Highlights - Most important sentences from the article

2019-03-05
1903.01869 | math.NA

The main focus of this paper is the characterization and exploitation of the asymptotic spectrum of … show more

Highlights - Most important sentences from the article

2018-12-15
1812.06295 | cs.DS

In this paper we show how to recover a spectral approximations to broad classes of structured matric… show more

Highlights - Most important sentences from the article

2019-03-15
1903.06350 | cs.DS

Subset selection for matrices is the task of extracting a column sub-matrix from a given matrix $B\i… show more Highlights - Most important sentences from the article 2016-10-10 1610.02962 | stat.ML This work studies the linear approximation of high-dimensional dynamical systems using low-rank dyna… show more Highlights - Most important sentences from the article 2018-11-05 1811.01885 | cs.DS Consider the following fundamental learning problem: given input examples$x \in \mathbb{R}^d\$ and t… show more

Highlights - Most important sentences from the article

2018-07-22
1807.09120 | cs.SY

Stabilization of linear systems with unknown dynamics is a canonical problem in adaptive control. Si… show more

Highlights - Most important sentences from the article

2018-12-11
1812.04590 | cs.SC

We consider the problem of computing the nearest matrix polynomial with a non-trivial Smith Normal F… show more

Highlights - Most important sentences from the article

2018-10-04
1810.02348 | cs.DS

In this paper we provide nearly linear time algorithms for several problems closely associated with … show more

Highlights - Most important sentences from the article

2017-06-08
1706.02586 | math.OC

In recent years, optimization theory has been greatly impacted by the advent of sum of squares (SOS)… show more

Highlights - Most important sentences from the article