Skip to main content

Questions tagged [sparsity]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
27 views

Enumeration of $k$-sparse 0/1-vectors of length $N$ [duplicate]

Let $\mathbf{x}$ be a $k$-sparse vector of length $N$ containing $k$ ones. There are $N\choose k$ such vectors and one would need $\log_2 {N\choose k}$ bits to enumerate all of them. Is there an ...
Ema's user avatar
  • 31
0 votes
1 answer
22 views

Setting sampling probability when sparsifying a non-negative weighted graph

Given a set of $mn$ non-negative edges, with what probability should one keep every edge $w_{ij}$ if we want $\sim pmn$ non-zero weights in our sparsified and every edge is sampled with a probability ...
meowcaroons's user avatar
1 vote
0 answers
30 views

Are all discontinuous levy processes sparse?

As described by the title, I would like to know if all discontinuous Levy processes (or jump Levy process, such as Poisson Process, Cauchy process, Gamma Process, etc.) are sparse processes? The ...
Username's user avatar
1 vote
1 answer
111 views

Sparse projection onto a single half-space

Let $x \in \mathbb{R}^n$ and $0 \neq a \in \mathbb{R}^n$ be a given vector and $b$ be a scalar such that the half-space defined by $a^{\top}x \leq b$ always include $0$. Question 1- Is there any ...
Saeed's user avatar
  • 175
2 votes
0 answers
62 views

When is the inverse of a sparse SPD matrix also sparse?

I have seen in several places that the inverse of a sparse matrix is generally not sparse, but I have failed to find more in-depth analysis than empirical or case-by-case studies. My question is the ...
Janjounoux's user avatar
0 votes
0 answers
48 views

In compressive sensing, what is the optimal dimension of the measurement matrix?

I have a sparse data vector ${\bf x} \in \mathbb{R}^n$, as part of a very large dataset. Approximately 75% of the data are zeros and I need to identify and work with a lower-dimensional version of ...
Zebra Fish's user avatar
2 votes
2 answers
185 views

Minimizing the number of non zero columns of a linear subspace of matrices

I'd like to solve the following minimization problem $$\min_{X_1,X_2} \mbox{nzc} (A+B_1X_1+B_2X_2)$$ where the $\mbox{nzc} (D)$ denotes the number of non-zero-columns in $D$, and where $X_i, A, B_i$ ...
Mathew's user avatar
  • 1,904
0 votes
1 answer
383 views

Show that the $\ell_p$ norm of $x$ as $p \to 0$ is the support of $x$

I have seen in many compressed sensing books which say that $$\lim_{p\to 0} \|x\|_p = \lim_{p\rightarrow 0}\left(\sum^n_{i=1}|x_i|^p\right)^{1/p} = \mbox{supp}\left(x\right)=\text{#} \{x_k:x_k \neq 0\}...
MathNoobs's user avatar
2 votes
0 answers
98 views

Group lasso with weighted parameters and L0 norm penalty

I have explored the following hard problem for a long time. I need some help for the (possibly) final steps. Specifically, \begin{equation}\tag{1} \min_{\mathbf{x}\in\mathbf{R}^n}\left\{ f(\mathbf{x}):...
suineg's user avatar
  • 385
5 votes
1 answer
298 views

Sparse Approximation in the Mahalanobis Distance

Given a vector $z \in \mathbb{R}^n$ and $k < n$, finding the best $k$-sparse approximation to $z$ in terms of the Euclidean distance means solving $$\min_{\{x \in \mathbb{R}^n : ||x||_0 \le k\}} ||...
Claudio Moneo's user avatar
1 vote
1 answer
258 views

What are the benefits of having fewer non-zero entries in the Cholesky decomposition of a matrix?

The question begins when I read the following paper. Carlotta Giannelli, Bert Jüttler, Hendrik Speleers, THB-splines: the truncated basis for hierarchical splines, Computer Aided Geometric Design, ...
yuxuan's user avatar
  • 117
0 votes
2 answers
207 views

Differentiable sparsity measure

I know that the sparsity of a matrix is the fraction of zero elements to the whole number of elements in a matrix. However, I wonder if there is a differentiable function or measure or approximation ...
Rythian's user avatar
7 votes
1 answer
374 views

Sparse PCA vs Orthogonal Matching Pursuit

Can't wrap my head around the difference between Sparse PCA and OMP. Both try to find a sparse linear combination. Of course, the optimization criteria is different. In Sparse PCA we have: \begin{...
Natan ZB's user avatar
1 vote
1 answer
263 views

Mutual coherence of two orthonormal bases, bound on number of non-zero entries

I'm supposed to prove the following: For two orthonormal bases $\Psi = (\psi_k)_{k = 1}^m$ and $\Phi = (\phi_k)_{k = 1}^m$ of $\mathbb R^m$ with mutual coherence $$\mu ([ \Psi \vert \Phi ]) = \max \...
jacques's user avatar
  • 539
2 votes
0 answers
39 views

Newton Polytope of a symmetric polynomial with few vertices

For an $n$-variate polynomial $f = \sum_{a_1,\dotsc,a_n} x_1^{a_1}x_2^{a_2} \cdots x_n^{a_n}$, its Newton polytope $P_f$ is defined as the convex hull of all exponent vectors in the support of $f$. ...
Pranav Bisht's user avatar
0 votes
0 answers
33 views

Sparse linear regression via precalculated full designmatrix

Let's suppose that we want to calculate a linear regression solution $X$ of data $Y$ via the design matrix $M$. The solution to such a problem is known as: $$X=M^{+}Y$$ Where $M$ results from ...
Robert Nowak's user avatar
2 votes
0 answers
98 views

Orthogonal projection into a sparse subspace with $s$ dimension

Traditional orthogonal projection of a given point $y \in \mathbb{R}^n$ into a closed and convex set $D\in \mathbb{R}^n$ is defined as the follwing: $$ P_D(y)=\arg\min_{x \in D}||x-y||_2^2 $$ Now ...
Saeed's user avatar
  • 175
1 vote
1 answer
967 views

Solving the Basis Pursuit Linear Program

Background: Suppose I have M samples of a signal $\mathbf{s}$ and I want to represent them by a linear combination of functions $\phi_{1}, \phi_{2}, \ldots, \phi_{L}$. I can do this by finding a ...
The Dude's user avatar
  • 1,079
1 vote
1 answer
129 views

Projection on modified L2-Ball

Suppose we are in $\mathbb{R}^n$ and we are given some integer $k$ such that $1 \leq k \leq n$. Let $\Vert x \Vert_0 = \#\{i\ |x_i \neq 0\}$ be the $L_0$-norm counting the number of non-zero entries ...
Doc's user avatar
  • 519
1 vote
0 answers
73 views

Minimization of $\|x\|_1$ subject to $\|Ax - y\| \leq \eta$ has an $m$-sparse solution when minimizer $x^*$ is unique

Given matrix $A \in \mathbb{R}^{m \times n}$, vector $y \in \mathbb{R}^m$, and scalar $ \eta \geq 0$, $$\begin{array}{ll} \underset{x \in \mathbb{R}^n}{\text{minimize}} & \|x\|_1\\ \text{subject ...
Lgate8's user avatar
  • 445
0 votes
1 answer
36 views

In order to induce group sparsity, can we use $\left \| A \right \|_{1,1}$ instead of $\left \| A \right \|_{1,2}$?

Let's define $\left \| A \right \|_{p,q}$ as follows: $$\left \| A \right \|_{p,q} = \sum_{i=1}^n \left \| \alpha^i \right \|_q^p$$. Where $\alpha^i$ is the i-th row of the matrix A. The above norm is ...
ashkan's user avatar
  • 103
0 votes
1 answer
216 views

vertical bar on vector

I am reading a paper and I have problem to understand the equation (this is the full paper) Assume that a one-dimensional discrete-time signal s of length N exhibits sparsity in certain orthonormal ...
AmandaKamphoff's user avatar
1 vote
1 answer
494 views

$l_{0}$-norm constrained quadratic programming optimization

I intend to solve for vector $ x \in \mathbb{R}^{N \times 1} $ by solving the following optimization problem \begin{align} \arg \min_{x} \tfrac{1}{2} \mathbf{x}^T Q\mathbf{x} + \mathbf{c}^T \mathbf{x} ...
SJ93's user avatar
  • 53
2 votes
1 answer
68 views

Efficiently enumerate the boolean matrix of sparsity k such that no rows and columns are all 0s.

Is there a way to enumerate the boolean matrix of $k$ entries of $1$ with no rows and columns all being $0$s? e.g. $k=1$, $\begin{bmatrix}1\end{bmatrix}$ $k=2$, $\begin{bmatrix}1 & 1\end{bmatrix}$ ...
Chen Xu's user avatar
  • 27
1 vote
1 answer
92 views

References for finding sparse solutions of an unconstrained non-convex optimization problem.

Given a function $f: \mathbb{R}^n \rightarrow \mathbb{R}$ where $n$ is large and $f$ is non-convex. The following characterises the sparse minimizer of $f$. $$ x^* = \arg \min_{x} f + ||x||_0 $$ where ...
user avatar
2 votes
1 answer
255 views

Is There a Connection Between Minimum $ {L}_{1} $ Norm Solution and LASSO?

I am reading a book about sparsity Statistical Learning with Sparsity: The Lasso and Generalizations. I want to know the relationship between the following two optimization problem: $$\min_{\beta} \| \...
XIONG ZENG's user avatar
0 votes
0 answers
89 views

Proving that a matrix is sparse

I have the following identity: $$L=(I-A)^TD^{-1} (I-A),$$ where $I$ is the identity matrix, $A$ is a $n \times n$ lower triangular matrix with no more than $m \ll n$ non-zero elements in each row and $...
coolsv's user avatar
  • 247
0 votes
0 answers
225 views

unique solution of l1 minimizer is sparse

I have tried to prove the following statement but after days of trying I couldn't! Suppose $\mathbf{X} \in \mathbb{R} ^ {N\times d}, \mathbf{y} \in \mathbb{R}^N$ and $\alpha > 0$. Show that for an ...
mohammad's user avatar
  • 199
1 vote
0 answers
39 views

Reconstruction of a probabilistically sparse signal

Consider we have a vector $\boldsymbol{x}_1^n$ which has a sparse structure in the sense that \begin{equation} \mathbb{P}(x_i=0)=\alpha>0. \end{equation} Further, assume that we have a sampled ...
Amin Charoo's user avatar
3 votes
2 answers
70 views

Stability of the Solution of $ {L}_{1} $ Regularized Least Squares (LASSO) Against Inclusion of Redundant Elements

The problem of finding $$ \substack{{\rm min}\\x}\left( \|Ax-b\|^2_2+\lambda \|x\|_1\right),$$ where $\|\cdot\|_2$ and $\|\cdot\|_1$ are the $L_2$ and $L_1$ norms, respectively, is usually called the ...
thedude's user avatar
  • 1,847
0 votes
0 answers
104 views

Sparse recovery by convex optimization

This is problem 10.3.6a in Vershynin's High Dimensional Probability book that I'm self-studying. I wasn't sure how to do this problem. I tried finding a bound on the set the solution comes from and ...
Enigma's user avatar
  • 3,929
3 votes
1 answer
614 views

If $ {L}_{0} $ Regularization Can be Done via the Proximal Operator, Why Are People Still Using LASSO?

I have just learned that a general framework in constrained optimization is called "proximal gradient optimization". It is interesting that the $\ell_0$ "norm" is also associated with a proximal ...
ArtificiallyIntelligent's user avatar
1 vote
1 answer
51 views

Can $L1$-regularization be applied in general case?

I am not very clear about how far $L1$-regularization can work. For example, let $x\in \mathbb{R}^n$. \begin{equation}\label{eq:Lasse1} \begin{aligned} &\max_{\mathbf{x}} & & f(\mathbf{x}...
sleeve chen's user avatar
  • 8,335
1 vote
1 answer
310 views

Understanding derivation of ADMM update rule for graphical lasso optimization by solving quadratic matrix equation

I'm trying to understand the derivation of an ADMM update rule in some convex optimization lecture notes by Emmanuel Candes [1]. In the course of the solution (on page 25-4 and 25-5), it is required ...
TheIntern's user avatar
  • 147
0 votes
1 answer
171 views

Sparse recovery with L1 shrinkage iteration for higher denominational image classification

For 2 months I have been studying sparse recovery and its applications for image classification and I have found that it's a broad area in mathematics which gives rise to a wide variety of ...
morteza's user avatar
  • 103
-1 votes
1 answer
23 views

Does the phrase "sparse bundle" mean anything?

This question is of no real consequence, it just popped into my head and I am curious about it. Apple uses a file format called the .sparsebundle for Time Machine backups on network drives. A ...
mweiss's user avatar
  • 23.7k
1 vote
0 answers
62 views

Encouraging sparse output in optimization problem

I am trying to define an optimization problem: $$ \min_\theta \sum_{x\in X} L(x, \theta, f_\theta(x),\delta_\theta(x)) + \lambda_s S(\delta_\theta(x)) $$ where $X$ is the dataset, $\theta$ are the ...
user3658307's user avatar
  • 10.5k
1 vote
1 answer
26 views

Continuous measure of number of large values in a sparse vector?

I'm looking for a measure that can give me an estimate of the number of significant values in a sparse vector, without using a threshold. For example, a measure $S$ might give some output like $S([0,...
geometrikal's user avatar
1 vote
0 answers
33 views

Is compressed sensing for digital signals or could also be applied for discrete time signals?

I was wondering if is compressed sensing for digital signals? or could also be applied for discrete time signals? What I mean is lets say I have a sampled but not quantized signals, can I find the ...
display name's user avatar
2 votes
1 answer
75 views

Sparsity of the inverse of a non-negative matrix

Let $A \in \mathbb{R}^{b \times b}$ be a matrix with non-negative entries. Suppose that $A$ is invertible. Further suppose that all the diagonal entries of $A$ are non-null. My claim is the following: ...
pulosky's user avatar
  • 665
0 votes
0 answers
92 views

In the Split-Bregman algorithm, what's the interpretation of the constraint strength parameter?

So, I've got the standard $L_1$ minimization problem: $\arg\min_x \{\|Ax-b\|_2^2+\lambda|Wx|_1\}$. I use Split-Bregman to solve this problem and it becomes $\arg\min_{x,d}\{\|Ax-b\|_2^2+\beta\|Wx-d\|^...
user26067's user avatar
  • 101
1 vote
0 answers
120 views

Matrix Sparsity Pattern

Suppose I have a matrix $H^{+} = (H^T H)^{-1} H^T$ where $H$ is a sparse matrix. Consider the case where only the sparsity pattern i.e. the zero elements of $H^{+}$ matrix is known, then would it be ...
Srinath's user avatar
  • 11
1 vote
0 answers
48 views

Does the optimal function in kernel method have a sparse representation?

The kernel least square method aims to solve the following problem, $$f^*=\arg \min_{f\in \mathcal{H}} E_{x,y}[(f(x)-y)^2]+\frac{\lambda}{2}\Vert f\Vert_{\mathcal{H}}$$ , where $\mathcal{H}$ is some ...
Kai Zhang's user avatar
1 vote
0 answers
607 views

Definition of sparsity

Considering the definition of sparsity in algebra, is it still correct to consider that a matrix / vector is sparse if the position of non-zero elements is known? Can a time-gating operation then be ...
Thomas's user avatar
  • 185
0 votes
0 answers
37 views

Why do sparse dictionary learning methods constrain the sparsity rather than the representation error?

The sparse coding problem is: $\underset{\boldsymbol{r}}{\text{min}} \left\Vert \boldsymbol{r} \right\Vert_0 ~s.t.~\textbf{x}=\text{D}\boldsymbol{r}$ Why do sparse dictionary learning algorithms ...
elliotp's user avatar
  • 155
5 votes
0 answers
578 views

Controlling the number of nonzero components in the LASSO solution

Let $A$ be a real $m \times n$ matrix. The Lasso optimization problem is $$ \text{minimize} \quad \frac12 \| Ax - b \|_2^2 + \lambda \| x \|_1 $$ The optimization variable is $x \in \mathbb R^n$. ...
littleO's user avatar
  • 52.5k
2 votes
4 answers
574 views

Non-sparse solution for a linear programming problem

I have formulated a linear program with equality, inequality and non-negativity constraints. My objective function is the minimization of a linear combination of decision variables (with different ...
Fred's user avatar
  • 123
0 votes
0 answers
38 views

Sparsity of DFT of powers of random sequence

Given a randomly chosen finite sequence of complex values ($a_0,a_1 \dots a_{N-1}$) such that their DFT is sparse, can anything be said about the sparsity of the DFT of the sequences ($a_0^{\frac{k}{N}...
Television's user avatar
0 votes
1 answer
272 views

Generating sparse vectors in a subspace (of $\mathbb{R}^n$)

I have an orthonormal basis for a given subspace (of $\mathbb{R}^n$). I am also given the sparsest ($l_0$ norm) vector direction (since $l_0$ norm is independent of scaling) belonging to the subspace (...
Television's user avatar
1 vote
0 answers
38 views

Highest sparsity vector in a vector subspace

I am aware of some work being done on recovering a sparse vector from a subspace over $\mathbb{R}$ (here). Has any work been done on finding the highest sparsity ($\min \{ \|x\|_0 : x\in \mathbb{S} \}$...
Television's user avatar