On the complexity of detecting positive eigenvectors of nonlinear cone maps

Lemmens, Bas; White, Lewis

doi:10.2140/involve.2019.12.141

Download this article
	For screen
	For printing

Recent Issues

The Journal

Submission Guidelines

Submission Form

Policies for Authors

Ethics Statement

ISSN: 1944-4184 (e-only)

ISSN: 1944-4176 (print)

Author Index

Coming Soon

Other MSP Journals

This article is available for purchase or by subscription. See below.

On the complexity of detecting positive eigenvectors of nonlinear cone maps

Bas Lemmens and Lewis White

Vol. 12 (2019), No. 1, 141–150

DOI: 10.2140/involve.2019.12.141

Abstract

In recent work with Lins and Nussbaum, the first author gave an algorithm that can detect the existence of a positive eigenvector for order-preserving homogeneous maps on the standard positive cone. The main goal of this paper is to determine the minimum number of iterations this algorithm requires. It is known that this number is equal to the illumination number of the unit ball $B_{v}$ of the variation norm, $∥ x ∥_{v} : = max_{i} x_{i} - min_{i} x_{i}$ on $V_{0} : = {x \in ℝ^{n} : x_{n} = 0}$ . In this paper we show that the illumination number of $B_{v}$ is equal to $(\binom{n}{⌈ n ∕ 2 ⌉})$ , and hence provide a sharp lower bound for the running time of the algorithm.

PDF Access Denied

We have not been able to recognize your IP address 13.59.82.167 as that of a subscriber to this journal.
Online access to the content of recent issues is by subscription, or purchase of single articles.

Please contact your institution's librarian suggesting a subscription, for example by using our journal-recommendation form. Or, visit our subscription page for instructions on purchasing a subscription.

You may also contact us at contact@msp.org
or by using our contact form.

Or, you may purchase this single article for USD 30.00:

Keywords

nonlinear maps on cones, positive eigenvectors, illumination problem, Hilbert's metric

Mathematical Subject Classification 2010

Primary: 47H07, 47H09

Secondary: 37C25

Milestones

Received: 29 August 2017

Revised: 21 November 2017

Accepted: 14 December 2017

Published: 31 May 2018

Communicated by Kenneth S. Berenhaut

Authors

Bas Lemmens
School of Mathematics, Statistics & Actuarial Science University of Kent Canterbury United Kingdom

Lewis White
School of Mathematics, Statistics & Actuarial Science University of Kent Canterbury United Kingdom

Vol. 12, No. 1, 2019