Quadproj: a Python package for projecting onto quadratic hypersurfaces
Authors: Loic Van Hoorebeeck
P.-A. Absil
Venue: NeurIPS 2022 Submitted (2022)
Keywords: nonconvex optimization
projection
quadratic hypersurface
quadric

Abstract: Quadratic hypersurfaces are a natural generalization of affine subspaces, and projections are elementary blocks of algorithms in optimization and machine learning. It is therefore intriguing that no proper studies and tools have been developed to tackle this nonconvex optimization problem. The quadproj package is a user-friendly and documented software that is dedicated to project a point onto a non-cylindrical central quadratic hypersurface.


Q a Python package for projecting onto quadratic hypersurfaces
Anonymous Author(s)
Affiliation Address
email
Abstract
Quadratic hypersurfaces are a natural generalization of affine subspaces, and projections are elementary blocks of algorithms in optimization and machine learning. It is therefore intriguing that no proper studies and tools have been developed to tackle this nonconvex optimization problem. The quadproj package is user- seer-friendly and documented software that is dedicated to project point onto non-cylindrical central quadratic hypersurface.
Introduction
Projection is one of the building blocks in many optimization softwares and machine learning algorithms (7] $2.91. Projection applications are multiple and include projected (gradient) methods 19. alternating projections [I splitting methods [13] and other proximal methods [8]
10
11 In this work, we focus on the orthogonal projection onto a quadratic surface. The motivation is threefold. First, quadratic (hyper)surfaces
natural generalization of affine subspaces. Because the projection onto an affine subspace is easy, it is tempting to trade accurate representation of the subspace (i.e., by approximating the quadratic hypersurface easiest projection, see [17] for an example of this kind. Being able to easily project onto a quadratic hypersurface, quadric, would remove the need of this trade-off. Second, the projection onto quadratic hypersurface is direct requirement of some applications: either in 2D and 3D spaces (mostly in image processing and computer-aided design) [14 24 [0], in larger dimensional spaces such as the nonconvex economic dispatch [22], the security of the gas network (20), and local learning methods 6 Finally, being able to project onto a quadratic hypersurface can seen as the first step to project onto the intersection of quadratic hypersurfaces. And, it is classical result of algebraic geometry that any projective variety is isomorphic to an intersection of quadratic hypersurfaces g Exercise 2.9].
13
14
a hyperplane) so to benefit from an
15
17
18
19
20
21
22
23
24 We implement the method proposed in 22 and package it into Python library. This method consists in solving the nonlinear system of equations associated to the KKT conditions of the nonlinear optimization problem used define the projection. To alleviate the complexity increase with the size of the problem (because the number of critical points grows linearly with the size of the problem), the
25
26
27
28 authors of [22] show that one of the global minima, that is, one of the projections, either corresponds
29 to the unique root of a nonlinear univariate function on a known interval, or belongs to finite set of
30 points to which closed-fie form available. The root of the univariate solution is readily obtained
31 Newton's 's method. Hence, the bottleneck of this method is the eigendecomposition of the matrix that
32
used define the quadric.
33 few other studies also discuss the projection onto quadrics. For the 2D or 3D cases, some methods
34
discussed in [15 44 10 but they do present the extension to the n--dimnnsional case. The
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

35 n--dimensional case is also analyzed in [2T], but their method is an iterative scheme that may converge
36 slowly and sometimes fails provide the exact projection.
37 The main goal of the present study is to democratize the exact method from 22 and thereby to save any potential user of quadratic projection from implementing it (or from falling back approximate the quadratic hypersurface by a hyperplane). Hence, emphasis is placed on i) the case of installation and ii) the user-friendliness of the package.
39
40
41
The package available in the Python Package Index (PyPi) 3 and on conda 2 The source code open- sourced on GitLab 4 and the documentation is available in [T]
Problem formulation
43
44 In this section, we first shortly present the projection problem. Then, we define the feasible set onto which the projection is performed (i.e., non-cylindrical central quadric).
46
2.1 The projection problem
The projection problem consists in mapping point x subset C of some Hilbert space H, [|ı that induced by the inner product :::
48
while minimizing the distance ||
Pre (a:) arg min ||ar x=11 (
#EC
49 For nonempty closed sets the projection is nonempty 22 Prop. 2.1]. is a singleton if C is also convex. For nonconvex closed set C, the solution may be singleton (e.g., Pre (z") with x C), 51 a larger finite set (e.g., the projection of any point that lies at mid distance between two hyperplanes onto the defined by the union of these hyperplanes),
infinite set (e.g., the projection of
53 the center of a sphere onto the sphere itself).
In the case where C' is hyperplane, there exists closed- form solution. If, for some vector b E H,
55 we have
C= { E Hb x)) + c= 0}
then the projection is the following singleton:
Pre (z") 1x0 0 (b, x:)) + cc b}.
|b|l
57
In this paper, we consider the canonical n--diennsonal Hilbert space I2" equipped with the
58 canonical inner product (uu, v) u u)) and its induced norm (//u||ı Fr = ||u||2 = Vu
59 In this settings, we present a toolbox for computing the projection onto a non-cylindrical central quadric.
80
61
2.2
Non-cylindrical central quadrics
82 quadric Q is the generalization of conic sections in spaces of dimension larger than two. is quadratic hypersurface of R² (of dimension 1) that can be characterized as
83
Q {a R
V (xx) x Ax bT + c= =))
(1)
84 with A E Rax= a symmetric matrix, b E R E IR and ((x): 1 - IR nonzero quadratic
85 function.
66 We can also represent the quadric with the extended coordinate vector x² E Rn+11 by inserting in the first of the coordinate Using the extended (symmetric) matrix
bt /2
A" =
(2)
6/2

---

68
the quadric is equally defined as
21
31
= a
E
1
(1
21
Fn)
A
0
In
69
Let r be the rank of (denoted (A) and p be the number of positive eigenvalues of A. Following the classification of [16) Theorem 3. we distinguish three types of real quadrics.
70
Type 1, conical quadrics: 5
n. 2
A+) rk(Al =r.
72
Type 2, central quadries: 5 S < nI, rk AA') rk A / =.
75
Type 3, parabolic quadries: 0 S rk( >
74 We also call cylindrical quadrics the central and conical quadrics with < n and the parabolic quadrics with 1--1
76 In this paper, we focus on nonempty central and non-cylindrical quadrics, that is, we consider
77 Eq. with A nonsingular and c A lb Indeed, when A nonsingular (i.e., when r = n)), one
4 78 can show that the condition + bb is equivalent to ((AA) rk(Al see [23 2.5] for more details.
Note that central quadrics are characterized by the existence of center A which corresponds to the center of symmetry of the quadric.
80
81
In 2D, non-cylindrical central quadric be circle, an ellipse, hyperbola. In 3D, it can be 89 a sphere, an ellipsoid, a one-sheet hyperboloid, or a two-sheet hyperboloid. In higher dimensional spaces, have hyperspheres, (hyper)ellipsoids, and hyperboloids.
2.3
The projection as an optimization problem
86 Let a E RR be the point to be projected, and be a non-cylindrical central quadric with parameters 87 A. b, and The optimization problem at hand reads
min a 12
I BER"
(3)
subject to T A. + b +-
simplify Eq. 3 Let VDVT A be an eigendecomposition of A, with V E " an orthogonal matrix whose columns are eigenvectors of A and D diag(A) the diagonal matrix whose entries the associated eigenvalues of A (denoted
Using appropriate coordinate transformation.
89
91 as À and sorted in descending order), and let = + 6Td + d Ad = b7
92 We can guarantee that > by flipping, if needed, the sign of A, b, and c. Indeed, E Q +>
T Ax + hT + c) (-b*) --
x: (-AA)) (-b) (-c) but if y -bt A then
94
95
we define the linear transformation
(a d)
T: 3
then Eg. 3 can be rewritten as
min #ER"
|| 111
(5)
subject to
Aaiy - 0.
37 with x T(#:). Note that Σn_ A = T Da, and that this new coordinate system the quadric is centered at the origin and aligned with the axes.

---

99
3
Method
100
There exists least one global solution of Eq. 5 because the objective function is real-valued, continuous and coercive function defined on nonempty closed set. Let us characterize one of these solutions.
102
103
The Lagrangian function of Eq. 5 with Lagrange multiplier and with diag(>) E IR = reads
104
a( p.) = (xc - x: xz)) - )²) + 1= Dx: 1).
105
Because the center does not belong the quadric, the linear independence constraint qualification
106
(LICQ) criterion is satisfied; using the KKT conditions, we have that any solution of Eq. (5) must be a solution of the following system of nonlinear equations [5] Chapter 4]:
107
(2(x= x + 2n 0.
V (Lx,
x Da
For μ $ x(A) = { X is eigenvalue of A}, write the first equations of Eq.
a(n) = (I + DD) a
Injecting this expression in the last equation of Eq. obtain univariate and extended-real 110 valued function
R:R p f(u) x()) Dx( -1
10
d
1.
(9)
1+ pd:
(=
.I .And any root of corresponds to a KKT point.
Proposition 2.20], the authors show that there is an optimal solution of Eq. (5) in the set (a²(")) X where
In [22]
113
114
(()) defined by Eq. (8), μ the unique root of f on given open interval I;
X is finite set of less than n elements.
115
The X is nonempty only if .0 is located at least principal axis of the quadric (or cquivalently, if at least one entry of x is 0), we refer to such cases degenerate cases (examples of which are depicted Fig. 4h. The details and the explicit formulation of I and X are given [22]
117
118
119
$ 2.5].
Our strategy solve Eq. 5 is to compute all elements of X and the root of on I, and choose among these points the one that is the closest to x.. We can then return the optimal solution of Eq. by using the inverse transformation
121
R -
T-)
Vx x + d.
(10)
We denote the (unique) returned solution as Pro (æ), which is one the optimal solutions of Eq. 5
123
124
The root of f is effectively obtained with Newton's method, which benefits from a superlinear convergence. Moreover, the number of iterations- which amounts evaluating and f' for cost O(n)-in typically low (no more than 20) and is independent from n. The computation of the finite 126
set X also costs (n). These computations are negligible with respect to the eigendecomposition. which is the bottleneck of the method. In particular, for 100 problems of size = 500, obtain mean exccution time of 0.065 s for the root-finding algorithm and a mean execution time 0.66 for the eigendecomposition (this experiment is available in dest_newtow py in 4
127
129
131
Another method for solving Eq. B (while trying to avoid the computation of the eigendecomposition of A) is to compute the gradient of the Lagrangian of Eq. (3) and to use a dedicated solver of systems of nonlinear equations. In this paper, we use the method optimize.
132
135
from the python package scipy. In Fig. [ we observe that for dimensions larger than 100, quadproj is faster than fsolve; each data point in Fig. D is the mean of 10 randomly generated instances, and the code of this experiment is available in test_ ceatt_eeeettionoocm
135
py 4. Besides, it is not guaranteed

---

x
10
0.4
Execution [5)
10-1
-0.4
quadproj time to build the quadric quadproj time project quadproj
-0.6
total
-0.6 -0.4
-02
400 6000
800
0.0
-0
Quadric size n
Figure Execution time methods.
Figure 2: Output of listing
137
that fsolve returns correct root (i.e., may converge to a critical point of Eq. that is not the global minimizer) nor that it will converge at all. Finally, fsolve cannot detect the additional solutions that appear in the degenerate cases; identifying that the case degenerate requires the cigendecomposition of A which would upsurge the execution time of such an fsolve-based method. For all these reasons, we decided not to make this fsolve-based method available in the quadproj package.
139
141
The quadproj package
143
144
Let us demonstrate in this section the use of quadproj through small code snippets. To avoid redundancy (e.g., the imports), the snippets should be run the current order.
145
146
4.1
The basics: a simple n-dimensional example
147
In listing D we create in line an object of class quadproj quadrics. Quadric c obtained by pro- viding dict (param) that contains the entries 'A', 'b', and "c" (corresponding the parameters A. b, and c). We then create a random initial point x0, project it onto the quadric, and check that the resulting point x_project is feasible by using the instance method Quadric. is ie__sisbbbe.
149
Listing 1: Projection onto n-dimensional quadric.
151
from quadproj import quadrics
from quadproj project import project
154
155
import numpy as
156
creating random data
158 dim 42
159 9 A np. random. rand (dim, dim)
180 - _A A.T # make sure that A is symmetric
random. rand (dim)
-1.42
16313
16414
18515
param ('A:: A, bb'; b, re": c} quadrics Quadric (param)
1871
16818
x0 np random...... rand (dim)
1
x.project project (Q, x0)
assert Q. feasibee (x..rjeee(. 'The projection is incorrect!'
5

---

1.0
Palxf)
Palkt
0.0
0.0
0.5
-0.5
-1.0
1.0
1.5
2.0
-10
1.5
(a) Output of listing
2
(b) Output of listing
Figure 3: Projection onto an ellipse.
4.2
Visualise the solution
172
The package also provides visualization tools. In listing 2
we compute and plot the projection of point onto an ellipse. The output is given in Fig. 3a where the projection x_project of onto the quadric is depicted as red point.
173
174
Listing 2: 2D visualization.
175
from quadproj project import Datt_xxx__rroeee
176
from os path import join
177 3
178
import matplotlib pyplot as plt
180
output_path
181
182 show False
np array ([[1, 0.11, [0.1, 211)
1851 np zeros (2)
188:2 -1
1873 = quadrics Quadric (('A): A, bb: b, ic?; c})
np. aprayryy 1])
19016 x projecet project (Q, x0)
18117
1928 fig. = Q.plo
xlot_=0=xx.roject (ax, q, x0, x_project)
194 ax exis('equll))
1981
plt. savefig (onepit@ouuutt..at...
')
A quick glance at Fig. 3a might give the (false) impression that the red point is not the closest one: this due to the difference scale between both axes, As a way to remedy this issue, we can either impose equal axes (by uncommenting line 20 in listing 2 or setting the argument flag_circle- cirglcirreeeuuee The
197
latter plots a circle centred x: with radius - Pro (x:) ||2. Because of the difference in the axis scaling, this circle (Fig. (3b) might resemble ellipse. However, it should not cross the quadric
199
and be tangent to the quadric at Pro (æ²): this is a visual proof of the solution optimality.
201
Listing 3: 2D visual proof of the optimality.
202 fig, ax (.plot
203 : poot_xo_x_projee (ax, q, x0, x_project, flag_
fig. savefig (join (output_path. callipse_circle.poe

---

1.00
0.75
0.25
Principal axes
-0.25
Pulic)
Principal anus
-0.6
0.75
Pgtct)
-1.00
-0.8
-1.00
-0.75
-0.50
-0.25
0.25
0.50
0.75
-0.5
0.5
1.0
(a) Output of listing
(b) Output of listing)
5
Figure 4: Degenerate projections.
4.3
Degenerate cases
206
For constructing a degenerate case, we cam:
207
Either construct quadric in standard form, i.e., with a diagonal matrix nul vector c=-1 1 and define some x0 with a least one entry equal to zero;
208
209
Or choose any quadric and select x0 to be on any principal axis of the quadric.
210
Let us illustrate the second option in listing We create x0 by applying the (inverse) standardization (see, Eq. (IO)) from some x0 with at least one entry equal to zero.
212
Here, we chose to close to the centre and on the longest axis of the ellipse so to be sure that there are multiple (two) solutions.
Recall that the program returns only one solution. Multiple solutions planned in future releases.
Listing 4: Degenerate projection onto an ellipse.
Q. non cot.oonssanddddieeddddeeeee (np array ([o, 0 1])
216 x_project project x0)
217: fig, ax = Q.
218 ax we.legend (1oc='(1oo= left')
plot_x0.x_ppojece (ax, q, x0, x_project, flag-circle=True)
2 fig savefig (join (output_patth
pdf
221 The output figure deiipeeedggeerateddd pdf is given in Fig. 4a can be seen that the reflection of x project along the largest ellipse axis (visible because show wwww_ssshseeeeeeeeeee weweiiippaaaxeesTtieee yields
223 another optimal solution.
224
Supported quadries
The class of supported quadrics are the non-cylindrical central quadrics. Visualization tools are available for the 2D and 3D cases: ellipses, hyperbolas, ellipsoids and hyperboloids.
226
227
4.4.1
Ellipses
See previous section for examples of projection onto ellipses.
229
4.4.2
Hyperbolas
230
illustrate listing the code to compute (degenerated) projection onto a hyperbola. The figure output is depicted in Fig. 4b
7

---

0.75
050
0.5
0.75
1.00
-1.0
-1.5
1.0
-2.0
0..00...... 0.2
-0.5
-2.01 -2.01.51.00
1.011$1.00.0 5.0.55.....00
0.0 -0.2-.44
0.1
(a) Output of listing 6
(b) Output of listing 7
Figure 5: Visualizations of 3D quadrics.
232 In this case, there is no root to the nonlinear function f from Eq. @ graphically, the second axis does intersect the hyperbola. This is not issue because solutions are obtained from the other set of KKT points (.
Listing 5: Degenerate projection onto a hyperbola.
A 0]
236 2 quadrics. ( A, "b': b, 'cl; c}) (np array (to, 0.1]))
237 x0 =
s.project project x0)
fig, xo___ptojecttee (ax, Q, x0, x_project, flag circleerce)
240 plot_x0_x_proox
x0
241 fig savefig (ottptttttt,,path "b pdf )))
degenerated
242
4.4.3 Ellipsoids
243
Similarly as the 2D case, we can plot an ellipsoid (listing [6) as in Fig. 5a To ease visualization, the function get get_turtn eet__urning-gif lets you write rotating gif.
Listing 6: Nondegenerate projection onto one-sheet hyperboloid.
245 dim = 3
= np.eyy eye (dim)
[0, 0]
248 [1, 1] 0.5
249
250 b = zeros (dim)
-1
param ('A': A, "b': b, 'c": c}
253 9 quadrics Quadric (param)
254
255
fig. Q.plot
25733
258
fig savefig (join (output_path, 'ellipsoid.pdf"
25815
get test_turninggee gif (step=4, gif gif_path=join (output_path) Q. t.type+' )))
4.4.4
One-sheet hyperboloid
In listing 7 we illustrate the case of one-sheet hyperboloid. Because it is currently not possible
253 to use equal axes 3D plots with matplotlib, the flag_ circle argument allows confirm the optimality of the solution despite the difference in the axis scales.

---

Listing 7: Nondegenerate projection onto one-shect hyperboloid.
265
[ 0]
266
param {'A:: A, "b': b, 'el: c} quadrica Quadric (param)
269
270
x0 up. pparray ([0.1, 0,42, -1.5])
x.project project x0)
27410 fig, ax Q.plot()
278 plot_x0_a xoop_xxet_ (ax, q, x0, x_project, flag.circle=True)
278
ax.gee_legend () remove
ax.view_init (elev=4, azim=42)
278
27815
dig.savefle. (join (output_path) chyprboloid,circle. pacirrcleepp)))...... ",)",, bbox_inches- tight')
280
4.4.5
Two-sheet hyperboloid
282
Finally, let us project a point onto a two-sheet hyperboloid: quadratic surface with two positive eigenvalues and one negative eigenvalue.
283
284
Listing is the program that produces Fig. This a degenerate case with two optimal solutions; quadproj returns one of these solutions (the one of the first orthant located in the right sheet of the hyperboloid).
286
Listing 8: Degenerate projection onto a two-shect hyperboloid.
np.eye ey.eye (3) 288 A [o, 0]
289 A [1, 1] = -2
[2, 2] = -1
np.
(3)
293 param ('A': A, 'b'; b, 'c': c}
294 quadrics Quadric (param)
x0 np. array 0.5, 0])
2971
29812
x x-project project (Q, x0)
29813
fig.
plot_ x0_xxO0___p__0 x.rojectteetttteee.eeeeeeeee..e. (ax, q, x0, x_project, fiag_circle-True)
5
Conclusion
303
In this paper, we presented a toolbox, called quadproj. for projecting any point onto a non-cylindrical central quadric. The problem written smooth nonlinear optimization problem and the solution is characterized through the KKT conditions.
304
305
We implemented and distributed this toolbox while focusing the user-friendliness and the simplicity of installation. is therefore possible to install from multiple sources (Pypi, conda, or from sources), and the projection is readily computed in few lines of code.
307
309
Further research includes extension to cylindrical central quadries, and more generally to conical and parabolic quadrics. Another research direction is to reduce the execution time of the algorithm by focusing on the bottleneck of the method (i.e., the eigendecomposition the symmetric matrix
311
used to define the quadric).

---

References
313
314
[1] Anonymous author. Documentation pages of quadproj.
hutpp://quadproo_pcccess
gitlab. jqj
Accesscdrrojjccccsssssee Accessed: 2022-04-13.
[2] Anonymous author. Quadproj: Anaconda.org. http:://mmacoaa..oo////////t//ap
317 Accessed: 2022-04-13.
318
[3] Anonymous author. Quadproj: pypi.org. https://ppp.oo///ppppccc//pppp// Ac-
319
cessed: 2022-04-13.
320
[4] Anonymous author. Quadproj: source code. https://gitlab httpllaaa.oomoooooo wtt.cooomm/uuueeceeeeeeeeeeeeeee http//uudpjopaccagge
quadproj Accessed: 2022-04-13.
[5] Mokhtar S. Bazaraa, Hanif D. Sherali, and C. M. Shetty, Nonlinear Programming: Theory and Algorithms. Wiley-Interscience, Hoboken, N.J, 3rd edition edition, May 2006.
323
324
[6] Scott Brown. Local Model Feature Transformations. PhD thesis, The University of South Alabama, may 2020.
325
326
[7] Mare Peter Deisenroth. Mathematics for Machine Learning. Cambridge University Press, Cambridge: New York, NY, 1st edition edition, April 2020.
327
328
[8] Joe Hariis. Algebraic Geometry: A First Course. Springer, New York, corrected edition edition, September 1992.
329
330
[9] Hamed Hassani, Mahdi Soltanolkotabi, and Amin Karbasi. Gradient methods for submodular maximization. Advances in Neural Information Processing Systems, 30, 2017.
[10] Shih-Feng Huang, Yung-Hsuan Wen, Chi-Hsiang Chu, and Chien-Chin Hsu. A Shape Approxi- mation for Medical Imaging Data. Sensors, 20(20):5879, January 2020.
333
334
[I]] A. S. Lewis, D. R. Luke, and Jérôme Malick. Local Linear Convergence for Alternating and Averaged Nonconvex Projections. Foundations of Computational Mathematics, 94):488--53, August 2009.
335
338
337
[12] A. S. Lewis and Jérôme Malick. Alternating Projections on Manifolds. Mathematics of Operations Reseurch, 33(1):216-234, February 2008
338
339
[13] Guoyin Li and Ting Kei Pong. Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems. Mathematical Programming, 159(1):371-411, September 2016.
341
342
[14] Gus K. Lott III. Direct Orthogonal Distance to Quadratic Surfaces in 3D. IEEE Transactions on Pattern Analysis and Machine Intelligence, 36(9):1888-188)) September 2014.
343
344
[15] D. Martínez Morera and J. Estrada Sarlabous. On the distance from a point quadric surface. Investigación Operacional, 14-21: September 2013.
345
[16] Boris Odehnal, Hellmuth Stachel, and Georg Glaeser. The Universe of Quadrics. Springer- Verlag, Berlin Heidelberg, 2020.
347
348
[17] Shanshan Pan, Jinbao Jian, and Linfeng Yang. A hybrid MILP and IPM approach for dynamic economic dispatch with valve-point effects. International Journal of Electrical Power & Energy Systems, 97:290 298, 2018
350
351
[18] Nicholas G. Polson, James G. Scott, and Brandon T. Willard. Proximal Algorithms in Statistics and Machine Learning. Statistical Science, 30(4), November 2015.
352
353
[19] Mahdi Soltanolkotabi. Learning ReLUs via gradient descent. Advances in neural information processing systems, 30, 2017.
354
[20] Chenhui Song, Jun Xiao, Guoqiang Zu, Ziyuan Hao, and Xinsong Zhang. Security region of natural gas pipeline network system: Concept, method and application. Energy, 217:1 19283, February 2021.
356
10

---

35e
[21]
Wilfredo Sosa and Fernanda MP Raupp. An algorithm for projecting a point onto a level set of a quadratic function. Optimization, pages 1-19, October 2020.
359
360
[22] Loic Van Hoorebeeck, P.-A. Absil, and Anthony Papavasiliou. Projection onto quadratic hypersurfaces, 2022. arviv: 2204.02087.
361
382
[23] Loic Van Hoorebeeck, P.-A. Absil, and Anthony Papavasiliou. Solving non-convex economic dispatch with valve-point effects and losses with guaranteed accuracy. International Journal of Electrical Power & Energy Systems, 134:107143, January 2022.
363
364
385
[24]
Caiyun Yang, Hiromasa Suzuki, Yutaka Ohtake, and Takashi Michikawa. Boundary smoothing for mesh segmentation. In 2009 11th IEEE International Conference on Computer-Aided Design and Computer Graphics, pages 241-248 August 2009.
366
367
Checklist
368
389
1. For all authors...
370
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We cannot deal with cylindrical and non-central quadrics.
373
374
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
375
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
378
2. If you are including theoretical results...
378
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
379
(b) Did you include complete proofs of all theoretical results? [N/A]
380
3. If you ran experiments..
381
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] See Section !
382
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
384
385
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [No] The experiment in Section 3 is obtained by running west_newteer -y, which also plots error bars.
387
388
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] It is shortly discussed in Section most of the execution times is spent in the eigendecomposition of A.
389
380
391
4. If you are using existing assets (c.g., code, data, models) or curating/releasing new assets...
392
(a) If your work uses existing assets, did you eite the creators? [N/A]
393
(b) Did you mention the license of the assets? [N/A]
394
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you' 're using/curating? [N/A]
387
398
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
399
5. If you used crowdsourcing conducted research with human subjects...
401
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
402
403
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
406
11


Reviews:
[{"review_id": "yLbctIH-uWg", "reviewer": "Reviewer_WidE", "summary": "This paper an introduction to a Python package implementing the method of projecting onto a central and non-cylindrical quadratic hypersurface (quadric) proposed in a recently posted arXiv manuscript [21]. Orthogonal projection onto a set is an important tool in machine learning as it is a basic building block of many learning algorithms. When the set onto which the projection is made is compact and convex the problem is relatively easy in the sense that the unique closest point exists and this point can be found using standard convex optimization algorithms. When the set is nonconvex, however, the problem needs to be tackled case by case. A quadric is a set of roots of a matrix quadratic equation characterized by the eigenvalues of the coefficient matrix $A$ of the quadratic term and the discriminant of the equation. This set is in general nonconvex. The recent manuscript [21, Proposition 2.20] provides  characteristics of a projected point (there can be multiple closest points from the input point since the set is nonconvex)  when the quadric is central (discriminant is nonzero) and non-cylindrical ($A$ is nonsingular), and also an algorithm [21, Algorithm 2] for computing it. This paper implements [21, Algorithm 2] in Python and build a package quadproj in order to democratize the algorithm. A review of the theory of [21] and exposition of how to use the quadproj package, with sample code snippets, are provided. ", "questions": "None.", "limitations": "Please see \"Strengths And Weaknesses\" section. In the present form, this paper looks as if it is an appendix to [21].", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "A strength of the paper is in the \"democratization\" of the algorithm for projection onto a quadric by writing an easy-to-use Python package. The package is designed so that construction of a quadric object, projection onto the quadric, and visualization of the solution is straightforward. The sample code snippets are also easy to follow. Indeed, visualization (in 2D or 3D cases)  is emphasized with a couple of figures. Also, the exposition is quite clear.\n\nA weakness is in novelty. All the theory and method in Sections 2 and 3 are treated in [21], so the contribution of this paper seems to be limited to Section 4, description of the quadproj package. I understand that careful and easy-to-use implementation of an algorithm is an important task, but for such an implementation is publishable to a premire conference and journal, I think more consideration is needed.  For example, in the editorial policy of the SIAM Journal on Scientific Computing (https://epubs.siam.org/journal/sisc/editorial-policy), which I believe is closest in scope with the paper, states for the \"Software and High-Performance Computing\" category as follows.\n\n> ... For software in particular, submitted papers should not be limited to describing a new package but must present the algorithmic or technological innovations that made the development of the software possible.\n\nUnfortunately, I do not see either algorithmic or technological innovation in the exposition of the package in this paper.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "tqsWm659Uer", "reviewer": "Reviewer_o4hv", "summary": "This paper is a short tutorial on a Python optimization package, which implements the method of the recent preprint [21], regarding the problem of projecting a given point of the Euclidean n-dimensional space onto a quadratic hypersurface. ", "questions": "1. What is the highest ambient dimension that the package can handle? Could the authors please report some indicative running times?\n\n2. How does this package compare to generic state-of-the-art homotopy continuation methods applied to the same problem?", "limitations": "Yes.", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\nCertainly, being able to project efficiently and accurately onto a quadratic hypersurface is very important, and the present paper concerns a promising step in this direction. Here is an additional reason for the significance of this problem, not mentioned in the paper: It is a classical fact in algebraic geometry, that any variety defined by homogeneous equations is isomorphic, via the so-called Veronese map, to a variety defined by quadratic equations (e.g., see Exercise 2.9, page 25, in “Algebraic Geometry: A First Course” by Joe Harris). Thus being able to efficiently and accurately project onto a single quadratic hypersurface, is the beginning of being able to project onto any variety, since the latter can be viewed as an intersection of quadratic hypersurfaces. \n\nWeakness:\n\nWhile a tutorial presenting a Python package for projecting onto quadratic hypersurfaces is certainly nice to have, I am of the impression that NeurIPS is not the appropriate venue for it.  Instead, I would have loved to see a short version of [21], with experiments or a case study highlighting the importance of the problem for the machine learning and data science community, and comparing with the state-of-the-art homotopy continuation methods for the same problem.\n\nBibliographic remark: I would like to bring to the authors’ attention the following papers and citations therein, regarding the problem of projecting onto hypersurfaces and varieties more generally:\n1. Draisma, Horobet, Ottaviani, Sturmfels, Thomas. “The Euclidean distance degree of an algebraic variety”. Foundations of Computational Mathematics.\n2. Breiding, Sottile, Woodcock. “Euclidean distance degree and mixed volume”. Foundations of Computational Mathematics.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "k0t_nHxwFVv", "reviewer": "Reviewer_47QC", "summary": "The paper describes a python package for projecting onto quadratic hypersurfaces. The basic problem it solves is to minimizing projection errors in Hilbert space subject to x^T A x + b^T x + c = 0. The authors show that with eigen decomposition of A, we can re-parametrize this problem and solve it with Newton's method. The paper also provides a number of example codes illustrating how to use the package. ", "questions": "Could you provide some studies about how this package tool scales with the growth of problem size. \n\nI would also like to see some high dimension application of the package.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n\n* clarity of writing\n* the tool seems to have broader usage in practice\n\nWeaknesses\n\n* Some computational performance studies are missing. It would be nice to include statistics of how this package tool scales with the growth of problem size. \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "1L3tk2cdOHo", "reviewer": "Reviewer_PLhJ", "summary": "Presents a library for computing projections onto a range of surfaces defined by Quadrics.", "questions": "N/A", "limitations": "This paper addresses a very narrow problem, and does not illustrate any concrete applications. I would have liked to see some demonstration of applications of the library.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper does a good job of describing the problem it solves and illustrating examples of how the library can be used to solve instances of problems within the class of projection problems it considers. I am supportive of papers on software libraries, they are explicitly within the scope of NeurIPS and contribute directly to the ML community. I don't have any larger critiques, the examples are easy to understand and the visuals are simple and clear.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject