Nonnegative matrix factorization is a popular data analysis tool able to extract significant features from nonnegative data. We consider an extension of this problem to handle functional data, using ...parametrizable nonnegative functions such as polynomials or splines. Factorizing continuous signals using these parametrizable functions improves both the accuracy of the factorization and its smoothness. We introduce a new approach based on a generalization of the Hierarchical Alternating Least Squares algorithm. Our method obtains solutions whose accuracy is similar to that of existing approaches using polynomials or splines, while its computational cost increases moderately with the size of the input, making it attractive for large-scale datasets.
Approximation of convex disks by inscribed and circumscribed polygons is a classical geometric problem whose study is motivated by various applications in robotics and computer aided design. We ...consider the following optimization problem: given integers
3
≤
n
≤
m
-
1
, find the value or an estimate of
r
(
n
,
m
)
=
max
P
∈
P
m
min
Q
∈
P
n
,
Q
⊇
P
|
Q
|
|
P
|
where
P
varies in the set
P
m
of all convex
m
-gons, and, for a fixed
m
-gon
P
, the minimum is taken over all
n
-gons
Q
containing
P
; here
|
·
|
denotes area. It is easy to prove that
r
(
3
,
4
)
=
2
, and from a result of Gronchi and Longinetti it follows that
r
(
n
-
1
,
n
)
=
1
+
1
n
tan
π
/
n
tan
2
π
/
n
for all
n
≥
6
. In this paper we show that every unit area convex pentagon is contained in a convex quadrilateral of area no greater than
3
/
5
thus determining the value of
r
(4, 5). In all cases, the equality is reached only for affine regular polygons.
We first show that a continuous function f is nonnegative on a closed set K⊆Hn if and only if (countably many) moment matrices of some signed measure dν=fdμ with suppμ=K are all positive semidefinite ...(if K is compact, μ is an arbitrary finite Borel measure with suppμ=K). In particular, we obtain a convergent explicit hierarchy of semidefinite (outer) approximations with no lifting of the cone of nonnegative polynomials of degree at most d. When used in polynomial optimization on certain simple closed sets K (e.g., the whole space Hn, the positive orthant, a box, a simplex, or the vertices of the hypercube), it provides a nonincreasing sequence of upper bounds which converges to the global minimum by solving a hierarchy of semidefinite programs with only one variable (in fact, a generalized eigenvalue problem). In the compact case, this convergent sequence of upper bounds complements the convergent sequence of lower bounds obtained by solving a hierarchy of semidefinite relaxations as in, e.g., J. B. Lasserre, SIAM J. Optim., 11 (2001), pp. 796-817. PUBLICATION ABSTRACT
We completely characterize sections of the cones of nonnegative polynomials, convex polynomials and sums of squares with polynomials supported on circuits, a genuine class of sparse polynomials. In ...particular, nonnegativity is characterized by an invariant, which can be immediately derived from the initial polynomial. Furthermore, nonnegativity of such polynomials
f
coincides with solidness of the amoeba of
f
, i.e., the Log-absolute-value image of the algebraic variety
V
(
f
)
⊂
(
C
∗
)
n
of
f
. These results generalize earlier works both in amoeba theory and real algebraic geometry by Fidalgo, Kovacec, Reznick, Theobald and de Wolff and solve an open problem by Reznick. They establish the first direct connection between amoeba theory and nonnegativity of real polynomials. Additionally, these statements yield a completely new class of nonnegativity certificates independent from sums of squares certificates.
We present a generalization of the notion of neighborliness to non-polyhedral convex cones. Although a definition of neighborliness is available in the non-polyhedral case in the literature, it is ...fairly restrictive as it requires all the low-dimensional faces to be polyhedral. Our approach is more flexible and includes, for example, the cone of positive-semidefinite matrices as a special case (this cone is not neighborly in general). We term our generalization Terracini convexity due to its conceptual similarity with the conclusion of Terracini’s lemma from algebraic geometry. Polyhedral cones are Terracini convex if and only if they are neighborly. More broadly, we derive many families of non-polyhedral Terracini convex cones based on neighborly cones, linear images of cones of positive-semidefinite matrices, and derivative relaxations of Terracini convex hyperbolicity cones. As a demonstration of the utility of our framework in the non-polyhedral case, we give a characterization based on Terracini convexity of the tightness of semidefinite relaxations for certain inverse problems.
Nonnegative matrix factorization is a key tool in many data analysis applications such as feature extraction, compression, and noise filtering. Many existing algorithms impose additional constraints ...to take into account prior knowledge and to improve the physical interpretation. This letter proposes a novel algorithm for nonnegative matrix factorization, in which the factors are modeled by nonnegative polynomials. Using a parametric representation of finite-interval nonnegative polynomials, we obtain an optimization problem without external nonnegativity constraints, which can be solved using conventional quasi-Newton or nonlinear least-squares methods. The polynomial model guarantees smooth solutions and may realize a noise reduction. A dedicated orthogonal compression enables a significant reduction of the matrix dimensions, without sacrificing accuracy. The overall approach scales well to large matrices. The approach is illustrated with applications in hyperspectral imaging and chemical shift brain imaging.
Verifying the positive semi-definiteness of a symmetric space tensor is an important and challenging topic in tensor computation. In this paper, we develop two methods to address the problem based on ...the theory of nonnegative polynomials which enables us to establish semi-definite programs to examine the positive semi-definiteness of a given symmetric space tensor. Moreover, using the similar idea, we can show that the minimal H-eigenvalue of a symmetric space tensor must be the optimal value of a semi-definite program. Computational results and discussions are provided to illustrate the significance of the results and the effectiveness of the proposed methods.
•We find two methods to verify the positive semi-definiteness of a symmetric space tensor.•The first method could verify the positive semi-definiteness of a symmetric space tensor in polynomial time.•The second method could verify the positive semi-definiteness of a symmetric space tensor in the large order case.•We discuss the method how to solve the H-eigenvalue of a symmetric space tensor.
PDF
