# Questions tagged [sparsity]

The tag has no usage guidance.

58 questions
Filter by
Sorted by
Tagged with
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 ...
• 31
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 ...
1 vote
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 ...
• 11
1 vote
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 ...
• 175
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 ...
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 ...
• 131
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$ ...
• 1,904
383 views

• 2,198
1 vote
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, ...
• 117
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 ...
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{...
• 95
1 vote
263 views

• 445
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 ...
• 103
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 ...
1 vote
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} ...
• 53
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}$ ...
• 27
1 vote
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 ...
255 views

• 52.5k
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 ...
• 123