Source author record

Ali Civril

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity Data Structures and Algorithms Information Theory math.IT

Catalog footprint

Research overview

2works

4topics

1close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2011arXiv

Exponential Inapproximability of Selecting a Maximum Volume Sub-matrix

Given a matrix $A \in \mathbb{R}^{m \times n}$ ( $n$ vectors in $m$ dimensions), and a positive integer $k < n$ , we consider the problem of selecting $k$ column vectors from $A$ such that the volume of the parallelepiped they define is maximum over all possible choices. We prove that there exists $δ<1$ and $c>0$ such that this problem is not approximable within $2^{-ck}$ for $k = δn$ , unless $P=NP$ .

preprint2011arXiv

Sparse Approximation is Hard

Given a redundant dictionary $Φ$ , represented by an $M \times N$ matrix ( $Φ\in \mathbb{R}^{M \times N}$ ) and a target signal $y \in \mathbb{R}^M$ , the \emph{sparse approximation problem} asks to find an approximate representation of $y$ using a linear combination of at most $k$ atoms. In this paper, a new complexity theoretic hardness result for sparse approximation problem is presented via considering a different measure of quality for the solution. It is argued that, from an algorithmic standpoint, the problem is more meaningful if it asks to maximize the norm of the target signal's projection onto the selected atoms which are represented by column vectors. Then, a multiplicative inapproximability result is established with this new measure, under a reasonable complexity theoretic assumption. This result in turn implies additive inapproximability for the problem with the standard measure. Specifically, if $ZPP \neq NP$ , all polynomial time algorithms which provide a $k$ -sparse vector $x$ should satisfy ${\|y-Φx\|}_2^2 \geq (1-c){\|y-Φx^*\|}_2^2 + c {\|y\|}_2^2,$ \noindent for $1/4(1-1/e) > c \geq 0$ where $x^*$ is the optimal $k$ -sparse solution. This result provides a quantification of the hardness for the case $y-Φx^* = 0$ , revealing more details about the inherent structure of the problem.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.