r"""Projection of :math:`\mathbf{V}` onto the simplex with cardinality constraint (maximum number of non-zero elements) and then scaled by `z`. .. math:: P\left(\mathbf{V}, \text{max_nz}, z\right) = \mathop{\arg \min}_{\substack{\mathbf{y} >= 0 \\ \sum_i \mathbf{y}_i = z} \\ ||p||_0 \le
(V, max_nz, z=1, axis=None, nx=None)
| 137 | |
| 138 | |
| 139 | def projection_sparse_simplex(V, max_nz, z=1, axis=None, nx=None): |
| 140 | r"""Projection of :math:`\mathbf{V}` onto the simplex with cardinality constraint (maximum number of non-zero elements) and then scaled by `z`. |
| 141 | |
| 142 | .. math:: |
| 143 | P\left(\mathbf{V}, \text{max_nz}, z\right) = \mathop{\arg \min}_{\substack{\mathbf{y} >= 0 \\ \sum_i \mathbf{y}_i = z} \\ ||p||_0 \le \text{max_nz}} \quad \|\mathbf{y} - \mathbf{V}\|^2 |
| 144 | |
| 145 | Parameters |
| 146 | ---------- |
| 147 | V: 1-dim or 2-dim ndarray |
| 148 | max_nz: int |
| 149 | Maximum number of non-zero elements in the projection. |
| 150 | If `max_nz` is larger than the number of elements in `V`, then |
| 151 | the projection is equivalent to `proj_simplex(V, z)`. |
| 152 | z: float or array |
| 153 | If array, len(z) must be compatible with :math:`\mathbf{V}` |
| 154 | axis: None or int |
| 155 | - axis=None: project :math:`\mathbf{V}` by :math:`P(\mathbf{V}.\mathrm{ravel}(), \text{max_nz}, z)` |
| 156 | - axis=1: project each :math:`\mathbf{V}_i` by :math:`P(\mathbf{V}_i, \text{max_nz}, z_i)` |
| 157 | - axis=0: project each :math:`\mathbf{V}_{:, j}` by :math:`P(\mathbf{V}_{:, j}, \text{max_nz}, z_j)` |
| 158 | |
| 159 | Returns |
| 160 | ------- |
| 161 | projection: ndarray, shape :math:`\mathbf{V}`.shape |
| 162 | |
| 163 | References |
| 164 | ---------- |
| 165 | .. [1] Sparse projections onto the simplex |
| 166 | Anastasios Kyrillidis, Stephen Becker, Volkan Cevher and, Christoph Koch |
| 167 | ICML 2013 |
| 168 | https://arxiv.org/abs/1206.1529 |
| 169 | """ |
| 170 | if nx is None: |
| 171 | nx = get_backend(V) |
| 172 | if V.ndim == 1: |
| 173 | return projection_sparse_simplex( |
| 174 | # V[nx.newaxis, :], max_nz, z, axis=1).ravel() |
| 175 | V[None, :], |
| 176 | max_nz, |
| 177 | z, |
| 178 | axis=1, |
| 179 | ).ravel() |
| 180 | |
| 181 | if V.ndim > 2: |
| 182 | raise ValueError("V.ndim must be <= 2") |
| 183 | |
| 184 | if axis == 1: |
| 185 | # For each row of V, find top max_nz values; arrange the |
| 186 | # corresponding column indices such that their values are |
| 187 | # in a descending order. |
| 188 | max_nz_indices = nx.argsort(V, axis=1)[:, -max_nz:] |
| 189 | max_nz_indices = nx.flip(max_nz_indices, axis=1) |
| 190 | |
| 191 | row_indices = nx.arange(V.shape[0]) |
| 192 | row_indices = row_indices.reshape(-1, 1) |
| 193 | print(row_indices.shape) |
| 194 | # Extract the top max_nz values for each row |
| 195 | # and then project to simplex. |
| 196 | U = V[row_indices, max_nz_indices] |