Continuity properties of the ball hull mapping

The ball hull mapping  β$\beta$ associates with each closed bounded convex set K$K$ in a Banach space its ball hull β(K)$\beta \left(K\right)$, defined as the intersection of all closed balls containing K$K$. We are concerned in this paper with continuity and Lipschitz continuity (with respect to the Hausdorff metric) of the ball hull mapping. It is proved that β$\beta$ is a Lipschitz map in finite dimensional polyhedral spaces. Both properties, finite dimension and polyhedral norm, are necessary for this result. Characterizing the ball hull mapping by means ofH$H$-convexity we show, with the help of a remarkable example from combinatorial geometry, that there exist norms with noncontinuous β$\beta$ map, even in finite dimensional spaces. Using this surprising result, we then show that there are infinite dimensional polyhedral spaces (in the usual sense of Klee) for which the map β$\beta$ is not continuous. A property known as ball stability implies that β$\beta$ has Lipschitz constant one. We prove that every Banach space of dimension greater than two can be renormed so that there is an intersection of closed balls for which none of its parallel bodies is an intersection of closed balls, thus lacking ball stability.     

Approximation of rank function and its application to the nearest low-rank correlation matrix

The rank function rank(.) is neither continuous nor convex which brings much difficulty to the solution of rank minimization problems. In this paper, we provide a unified framework to construct the approximation functions of rank(.), and study their favorable properties. Particularly, with two families of approximation functions, we propose a convex relaxation method for the rank minimization problems with positive semidefinite cone constraints, and illustrate its application by computing the nearest low-rank correlation matrix. Numerical results indicate that this convex relaxation method is comparable with the sequential semismooth Newton method (Li and Qi in SIAM J Optim 21:1641–1666, 2011) and the majorized penalty approach (Gao and Sun, 2010) in terms of the quality of solutions.     

$$S_{1/2}$$ regularization methods and fixed point algorithms for affine rank minimization problems

The affine rank minimization problem is to minimize the rank of a matrix under linear constraints. It has many applications in various areas such as statistics, control, system identification and machine learning. Unlike the literatures which use the nuclear norm or the general Schatten \(q~ (0<q<1)\) quasi-norm to approximate the rank of a matrix, in this paper we use the Schatten 1 / 2 quasi-norm approximation which is a better approximation than the nuclear norm but leads to a nonconvex, nonsmooth and non-Lipschitz optimization problem. It is important that we give a global necessary optimality condition for the \(S_{1/2}\) regularization problem by virtue of the special objective function. This is very different from the local optimality conditions usually used for the general \(S_q\) regularization problems. Explicitly, the global necessary optimality condition for the \(S_{1/2}\) regularization problem is a fixed point inclusion associated with the singular value half thresholding operator. Naturally, we propose a fixed point iterative scheme for the problem. We also provide the convergence analysis of this iteration. By discussing the location and setting of the optimal regularization parameter as well as using an approximate singular value decomposition procedure, we get a very efficient algorithm, half norm fixed point algorithm with an approximate SVD (HFPA algorithm), for the \(S_{1/2}\) regularization problem. Numerical experiments on randomly generated and real matrix completion problems are presented to demonstrate the effectiveness of the proposed algorithm.     

A weak Grothendieck compactness principle for Banach spaces with a symmetric basis

The Grothendieck compactness principle states that every norm compact subset of a Banach space is contained in the closed convex hull of a norm null sequence. In Dowling et al. (J Funct Anal 263(5):1378–1381, 2012), an analogue of the Grothendieck compactness principle for the weak topology was used to characterize Banach spaces with the Schur property. Using a different analogue of the Grothendieck compactness principle for the weak topology, a characterization of the Banach spaces with a symmetric basis that are not isomorphic to $\ell ^1$ and do not contain a subspace isomorphic to $c_0$ is given. As a corollary, it is shown that, in the Lorentz space $d(w,1)$ , every weakly compact set is contained in the closed convex hull of the rearrangement invariant hull of a norm null sequence.     

On the rank of a spectral function

Let P(x), 0 x 1, be an absolutely continuous spectral function in the separable Hilbert spacesS. If the vectors h_j, j=1, 2, ..., s; s are such that the set P(x)h_j is complete inS, then the rank of the function P(x) equals the general rank of the matrix-function d/dxP(x)h_i,h_js₁.Translated from Matematicheskie Zametki, Vol. 5, No. 4, pp. 457–460, April, 1969.     

On approximations of rank one -perturbations

Approximations of rank one -perturbations of self-adjoint operators by operators with regular rank one perturbations are discussed. It is proven that in the case of arbitrary not semibounded operators such approximations in the norm resolvent sense can be constructed without any renormalization of the coupling constant. Approximations of semibounded operators are constructed using rank one non-symmetric regular perturbations.

     

The geometry of Nielsen's Hull for a Kleinian group in space and quasi-conformal mappings

A method of investigating the geometry of the boundary of Nielsen's convex hull is developed. It is based on the consideration of a covering of the discontinuity set of a Kleinian group in space by maximal balls. As application, n-dimensional analogues of a theorem of Sullivan is proved and a new phenomenon is discovered: the presence of isometrically undevelopable singularities of the boundary of Nielsen's hull for a spatial Kleinian group. This presents a new information about deformations of spatial conformal structures on manifolds.     

On the rank of odd hyper-quasi-polynomials

Given any nonzero entire function g: ? → ?, the complex linear space F(g) consists of all entire functions f decomposable as f(z + w)g(z - w)=φ₁(z)ψ₁(w)+???+ φ_n(z)ψ_n(w) for some φ₁, ψ₁, …, φ_n, ψ_n: ? → ?. The rank of f with respect to g is defined as the minimum integer n for which such a decomposition is possible. It is proved that if g is an odd function, then the rank any function in F(g) is even.     

Finding the nearest point in A polytope

A terminating algorithm is developed for the problem of finding the point of smallest Euclidean norm in the convex hull of a given finite point set in Euclideann-space, or equivalently for finding an optimal hyperplane separating a given point from a given finite point set. Its efficiency and accuracy are investigated, and its extension to the separation of two sets and other convex programming problems described.     

Aggregation of ranked votes considering different relative gaps between rank positions

This paper considers ranked voting systems to determine the rank order of candidates who compete for a limited number of positions. We show that the preferential voting problems based on the data envelopment analysis (DEA) (Wang et al, 2007) can be solved using the extreme points of constraints on rank position importance incorporated in the formulation. This is basically due to the fact that the so-called inverse positive property of the constraints makes it possible to easily find their extreme points. Further, we emphasize that this finding is not restricted to Wang et al’s two linear models, but is also applicable to other DEA-based preferential voting problems, which include the constraints accounting for different relative gaps between rank positions.     

Accelerate overrelaxation methods for rank deficient linear systems

In this paper, we apply accelerated overrelaxation (AOR) methods to find the least square solution of minimal norm to the linear system

Ay=b

where is a matrix of rank r and . We first augment the system to a block 4×4 consistent system, and then split the augmented coefficient matrix by AOR subproper splitting. Intervals for the two relaxation parameters where the AOR iteration matrix is semiconvergent are presented. Also, we provide a method to compute the least square solution of minimal norm to the system.     

Spectrahedral cones generated by rank 1 matrices

Let \(\mathcal{S}_+^n \subset \mathcal{S}^n\) be the cone of positive semi-definite matrices as a subset of the vector space of real symmetric \(n \times n\) matrices. The intersection of \(\mathcal{S}_+^n\) with a linear subspace of \(\mathcal{S}^n\) is called a spectrahedral cone. We consider spectrahedral cones K such that every element of K can be represented as a sum of rank 1 matrices in K. We shall call such spectrahedral cones rank one generated (ROG). We show that ROG cones which are linearly isomorphic as convex cones are also isomorphic as linear sections of the positive semi-definite matrix cone, which is not the case for general spectrahedral cones. We give many examples of ROG cones and show how to construct new ROG cones from given ones by different procedures. We provide classifications of some subclasses of ROG cones, in particular, we classify all ROG cones for matrix sizes not exceeding 4. Further we prove some results on the structure of ROG cones. We also briefly consider the case of complex or quaternionic matrices. ROG cones are in close relation with the exactness of semi-definite relaxations of quadratically constrained quadratic optimization problems or of relaxations approximating the cone of nonnegative functions in squared functional systems.     

Arithmetical rank of binomial ideals

In this paper, we investigate the arithmetical rank of a binomial ideal J. We provide lower bounds for the binomial arithmetical rank and the J-complete arithmetical rank of J. Special attention is paid to the case where J is the binomial edge ideal of a graph. We compute the arithmetical rank of such an ideal in various cases.     

A variational approach of the rank function

In the same spirit as the one of the paper (Hiriart-Urruty and Malick in J. Optim. Theory Appl. 153(3):551–577, 2012) on positive semidefinite matrices, we survey several useful properties of the rank function (of a matrix) and add some new ones. Since the so-called rank minimization problems are the subject of intense studies, we adopt the viewpoint of variational analysis, that is the one considering all the properties useful for optimizing, approximating or regularizing the rank function.     

A note on the split rank of intersection cuts

In this note, we present a simple geometric argument to determine a lower bound on the split rank of intersection cuts. As a first step of this argument, a polyhedral subset of the lattice-free convex set that is used to generate the intersection cut is constructed. We call this subset the restricted lattice-free set. It is then shown that élog₂ (l)ù{\lceil \log_2 (l)\rceil} is a lower bound on the split rank of the intersection cut, where l is the number of integer points lying on the boundary of the restricted lattice-free set satisfying the condition that no two points lie on the same facet of the restricted lattice-free set. The use of this result is illustrated by obtaining a lower bound of élog₂( n+1) ù{\lceil \log_2( n+1) \rceil} on the split rank of n-row mixing inequalities.     

Rank-one convex hulls in \mathbb{R}^{2\times2}

We study the rank-one convex hull of compact sets . We show that if K contains no two matrices whose difference has rank one, and if K contains no four matrices forming a T ₄ configuration, then the rank-one convex hull K ^rc is equal to K. Furthermore, we give a simple numerical criterion for testing for T ₄ configurations. Received: 20 August 2003, Accepted: 3 March 2004, Published online: 12 May 2004 Mathematics Subject Classification (2000): 49J45, 52A30 An erratum to this article can be found at     

Low rank matrix recovery from rank one measurements

We study the recovery of Hermitian low rank matrices $X\in {\mathbb{C}}^{n\times n}$ from undersampled measurements via nuclear norm minimization. We consider the particular scenario where the measurements are Frobenius inner products with random rank-one matrices of the form $a_j{a}_j^{?}$ for some measurement vectors $a_1,\dots ,a_m$, i.e., the measurements are given by $b_j=\mathrm{tr}(X{a}_j{a}_j^{?})$. The case where the matrix $X=x{x}^{?}$ to be recovered is of rank one reduces to the problem of phaseless estimation (from measurements $b_j=|〈x,a_j〉{|}^2$) via the PhaseLift approach, which has been introduced recently. We derive bounds for the number m of measurements that guarantee successful uniform recovery of Hermitian rank r matrices, either for the vectors $a_j$, $j=1,\dots ,m$, being chosen independently at random according to a standard Gaussian distribution, or $a_j$ being sampled independently from an (approximate) complex projective t-design with $t=4$. In the Gaussian case, we require $m\ge Crn$ measurements, while in the case of 4-designs we need $m\ge \mathit{Cr}n\log ?(n)$. Our results are uniform in the sense that one random choice of the measurement vectors $a_j$ guarantees recovery of all rank r-matrices simultaneously with high probability. Moreover, we prove robustness of recovery under perturbation of the measurements by noise. The result for approximate 4-designs generalizes and improves a recent bound on phase retrieval due to Gross, Krahmer and Kueng. In addition, it has applications in quantum state tomography. Our proofs employ the so-called bowling scheme which is based on recent ideas by Mendelson and Koltchinskii.     

KT-nearfields of rank 2

Summary Nearfields of rank 2 over their kernel which are not Dickson nearfields have recently been constructed by H. Zassenhaus. Here it is shown that KT-nearfields of rank 2 over their kernels and of characteristic 2 are necessarily Dickson nearfields which are coupled to quadratic field extensions and their Dickson group is isomorphic to ₂. Using results of Gröger one obtains all KT-nearfields of rank 2 over the field of rational numbers.     

An FPTAS for minimizing the product of two non-negative linear cost functions

We consider a quadratic programming (QP) problem (Π) of the form min x ^T C x subject to Ax ≥ b, x ≥ 0 where \({C\in {\mathbb R}^{n \times n}_+, {\rm rank}(C)=1}\) and \({A\in {\mathbb R}^{m \times n}, b\in {\mathbb R}^m}\) . We present an fully polynomial time approximation scheme (FPTAS) for this problem by reformulating the QP (Π) as a parameterized LP and “rounding” the optimal solution. Furthermore, our algorithm returns an extreme point solution of the polytope. Therefore, our results apply directly to 0–1 problems for which the convex hull of feasible integer solutions is known such as spanning tree, matchings and sub-modular flows. They also apply to problems for which the convex hull of the dominant of the feasible integer solutions is known such as s, t-shortest paths and s, t-min-cuts. For the above discrete problems, the quadratic program Π models the problem of obtaining an integer solution that minimizes the product of two linear non-negative cost functions.     

Fixed point and Bregman iterative methods for matrix rank minimization

The linearly constrained matrix rank minimization problem is widely applicable in many fields such as control, signal processing and system identification. The tightest convex relaxation of this problem is the linearly constrained nuclear norm minimization. Although the latter can be cast as a semidefinite programming problem, such an approach is computationally expensive to solve when the matrices are large. In this paper, we propose fixed point and Bregman iterative algorithms for solving the nuclear norm minimization problem and prove convergence of the first of these algorithms. By using a homotopy approach together with an approximate singular value decomposition procedure, we get a very fast, robust and powerful algorithm, which we call FPCA (Fixed Point Continuation with Approximate SVD), that can solve very large matrix rank minimization problems (the code can be downloaded from http://www.columbia.edu/~sm2756/FPCA.htm for non-commercial use). Our numerical results on randomly generated and real matrix completion problems demonstrate that this algorithm is much faster and provides much better recoverability than semidefinite programming solvers such as SDPT3. For example, our algorithm can recover 1000 × 1000 matrices of rank 50 with a relative error of 10^?5 in about 3?min by sampling only 20% of the elements. We know of no other method that achieves as good recoverability. Numerical experiments on online recommendation, DNA microarray data set and image inpainting problems demonstrate the effectiveness of our algorithms.